Algorithm
A Fibonacci Heap is a data structure used in computer science for implementing a priority queue. It was designed by Michael L. Fredman and Robert E. Tarjan in 1984 and is an extension of the binomial heap. Fibonacci Heaps have some advantages over other types of heaps, especially when it comes to certain operations like decrease key and merging.
Here are some key characteristics and operations associated with Fibonacci Heaps:
-
Structure:
- A Fibonacci Heap is a collection of trees, where each tree is a min-heap.
- Unlike a binomial heap, the trees in a Fibonacci Heap can have any shape, leading to a more flexible structure.
-
Key Operations:
- Insertion: O(1) time complexity.
- Union (Merge): O(1) time complexity. This is one of the main advantages of Fibonacci Heaps. When merging two Fibonacci Heaps, the roots of the two heaps are simply concatenated.
- Extract-Min (Deletion of minimum element): O(log n) amortized time complexity, where n is the number of elements in the heap. This is because during the extraction of the minimum element, some trees may be cut and consolidated.
-
Decrease Key:
- Decreasing the key of an element is done in O(1) time. This is a significant advantage over other heap types.
- The decrease key operation allows efficiently updating the priority of an element in the heap.
-
Amortized Analysis:
- The amortized time complexity of most operations is better than that of other types of heaps, making Fibonacci Heaps suitable for certain applications.
However, despite its theoretical advantages, Fibonacci Heaps are not always the best choice in practice. The constant factors in their operations can make them slower for small to moderately-sized datasets. As a result, other types of heaps, such as binary heaps or binomial heaps, are often preferred for general-purpose use. Fibonacci Heaps are particularly useful in situations where there are many decrease key operations, such as in certain graph algorithms like Dijkstra's algorithm and Prim's algorithm.
Code Examples
#1 Fibonacci Heap implement in Python
Code -
Python Programming
class FibonacciHeapNode:
def __init__(self, key):
self.key = key
self.degree = 0
self.marked = False
self.parent = None
self.child = None
self.next = self
self.prev = self
class FibonacciHeap:
def __init__(self):
self.min_node = None
self.num_nodes = 0
def insert(self, key):
new_node = FibonacciHeapNode(key)
if self.min_node is None:
self.min_node = new_node
else:
self._link(self.min_node, new_node)
self.num_nodes += 1
def extract_min(self):
min_node = self.min_node
if min_node is not None:
if min_node.child is not None:
child = min_node.child
while True:
next_child = child.next
child.prev = min_node.prev
child.next = min_node.next
min_node.prev.next = child
min_node.next.prev = child
child.parent = None
if next_child == min_node.child:
break
child = next_child
min_node.prev.next = min_node.next
min_node.next.prev = min_node.prev
if min_node == min_node.next:
self.min_node = None
else:
self.min_node = min_node.next
self._consolidate()
self.num_nodes -= 1
return min_node.key if min_node is not None else None
def decrease_key(self, node, new_key):
if new_key > node.key:
raise ValueError("New key is greater than the current key")
node.key = new_key
parent = node.parent
if parent is not None and node.key < parent.key:
self._cut(node, parent)
self._cascading_cut(parent)
if node.key < self.min_node.key:
self.min_node = node
def _link(self, root1, root2):
root2.prev.next = root2.next
root2.next.prev = root2.prev
root2.prev = root2
root2.next = root2
if root1.child is None:
root1.child = root2
else:
self._insert_before(root2, root1.child)
root2.parent = root1
root1.degree += 1
root2.marked = False
def _consolidate(self):
max_degree = int(self.num_nodes ** 0.5)
aux_list = [None] * (max_degree + 1)
current = self.min_node
roots = []
while True:
roots.append(current)
current = current.next
if current == self.min_node:
break
for root in roots:
degree = root.degree
while aux_list[degree] is not None:
other = aux_list[degree]
if root.key > other.key:
root, other = other, root
self._link(root, other)
aux_list[degree] = None
degree += 1
aux_list[degree] = root
self.min_node = None
for node in aux_list:
if node is not None:
if self.min_node is None:
self.min_node = node
elif node.key < self.min_node.key:
self.min_node = node
def _cut(self, child, parent):
if child.next == child:
parent.child = None
else:
child.prev.next = child.next
child.next.prev = child.prev
if parent.child == child:
parent.child = child.next
parent.degree -= 1
self._insert_before(child, self.min_node)
child.parent = None
child.marked = False
def _cascading_cut(self, node):
parent = node.parent
if parent is not None:
if not node.marked:
node.marked = True
else:
self._cut(node, parent)
self._cascading_cut(parent)
def _insert_before(self, node, target):
node.prev = target.prev
node.next = target
target.prev.next = node
target.prev = node
# Example Usage
if __name__ == "__main__":
fibonacci_heap = FibonacciHeap()
fibonacci_heap.insert(3)
fibonacci_heap.insert(8)
fibonacci_heap.insert(2)
print(f"Fibonacci Heap: {fibonacci_heap.extract_min()}") # Output: 2
#2 Fibonacci Heap implement in Java
Code -
Python Programming
import java.util.*;
class FibonacciHeapNode {
int key;
int degree;
boolean marked;
FibonacciHeapNode parent;
FibonacciHeapNode child;
FibonacciHeapNode prev;
FibonacciHeapNode next;
public FibonacciHeapNode(int key) {
this.key = key;
this.degree = 0;
this.marked = false;
this.parent = null;
this.child = null;
this.prev = this;
this.next = this;
}
}
public class FibonacciHeap {
private FibonacciHeapNode minNode;
private int size;
public FibonacciHeap() {
this.minNode = null;
this.size = 0;
}
public boolean isEmpty() {
return minNode == null;
}
public void insert(int key) {
FibonacciHeapNode node = new FibonacciHeapNode(key);
if (minNode == null) {
minNode = node;
} else {
mergeLists(minNode, node);
if (node.key < minNode.key) {
minNode = node;
}
}
size++;
}
private void mergeLists(FibonacciHeapNode root1, FibonacciHeapNode root2) {
FibonacciHeapNode temp1 = root1.next;
root1.next = root2.next;
root2.next.prev = root1;
root2.next = temp1;
temp1.prev = root2;
}
public int getMin() {
if (isEmpty()) {
throw new NoSuchElementException("Heap is empty");
}
return minNode.key;
}
public int deleteMin() {
if (isEmpty()) {
throw new NoSuchElementException("Heap is empty");
}
FibonacciHeapNode deletedMin = minNode;
if (minNode.child != null) {
FibonacciHeapNode child = minNode.child;
do {
FibonacciHeapNode nextChild = child.next;
minNode.child = nextChild;
mergeLists(minNode, child);
child.parent = null;
child = nextChild;
} while (child != minNode.child);
}
removeNodeFromList(minNode);
if (minNode.next == minNode) {
minNode = null;
} else {
minNode = minNode.next;
consolidate();
}
size--;
return deletedMin.key;
}
private void consolidate() {
int maxDegree = (int) Math.floor(Math.log(size) / Math.log(2));
List<FibonacciHeapNode> degreeTable = new ArrayList<>(maxDegree + 1);
for (int i = 0; i <= maxDegree; i++) {
degreeTable.add(null);
}
List<FibonacciHeapNode> roots = new ArrayList<>();
FibonacciHeapNode current = minNode;
do {
roots.add(current);
current = current.next;
} while (current != minNode);
for (FibonacciHeapNode root : roots) {
int degree = root.degree;
while (degreeTable.get(degree) != null) {
FibonacciHeapNode other = degreeTable.get(degree);
if (root.key < other.key) {
FibonacciHeapNode temp = root;
root = other;
other = temp;
}
link(other, root);
degreeTable.set(degree, null);
degree++;
}
degreeTable.set(degree, root);
}
minNode = null;
for (FibonacciHeapNode root : degreeTable) {
if (root != null) {
if (minNode == null) {
minNode = root;
} else {
mergeLists(minNode, root);
if (root.key < minNode.key) {
minNode = root;
}
}
}
}
}
private void link(FibonacciHeapNode child, FibonacciHeapNode parent) {
removeNodeFromList(child);
child.marked = false;
child.parent = parent;
if (parent.child == null) {
parent.child = child;
child.next = child;
child.prev = child;
} else {
mergeLists(parent.child, child);
}
parent.degree++;
}
private void removeNodeFromList(FibonacciHeapNode node) {
node.prev.next = node.next;
node.next.prev = node.prev;
node.next = node;
node.prev = node;
}
// Example usage
public static void main(String[] args) {
FibonacciHeap fibonacciHeap = new FibonacciHeap();
fibonacciHeap.insert(5);
fibonacciHeap.insert(3);
fibonacciHeap.insert(8);
fibonacciHeap.insert(1);
System.out.println("Min element: " + fibonacciHeap.getMin()); // Output: 1
int minElement = fibonacciHeap.deleteMin();
System.out.println("Deleted Min element: " + minElement); // Output: 1
System.out.println("New Min element: " + fibonacciHeap.getMin()); // Output: 3
}
}
#3 Fibonacci Heap implement in C
Code -
C Programming
#include <stdio.h>
#include <stdlib.h>
// Node structure for the Fibonacci Heap
typedef struct Node {
int key;
int degree;
int marked;
struct Node* parent;
struct Node* child;
struct Node* left;
struct Node* right;
} Node;
// Fibonacci Heap structure
typedef struct FibonacciHeap {
Node* min;
int size;
} FibonacciHeap;
// Function to create a new node with a given key
Node* createNode(int key) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->key = key;
newNode->degree = 0;
newNode->marked = 0;
newNode->parent = NULL;
newNode->child = NULL;
newNode->left = newNode;
newNode->right = newNode;
return newNode;
}
// Function to create an empty Fibonacci Heap
FibonacciHeap* createFibonacciHeap() {
FibonacciHeap* newHeap = (FibonacciHeap*)malloc(sizeof(FibonacciHeap));
newHeap->min = NULL;
newHeap->size = 0;
return newHeap;
}
// Function to link two trees of the same degree
void link(Node* min, Node* newChild) {
newChild->left->right = newChild->right;
newChild->right->left = newChild->left;
newChild->left = newChild->right = newChild;
newChild->parent = min;
if (min->child == NULL) {
min->child = newChild;
} else {
newChild->right = min->child;
newChild->left = min->child->left;
min->child->left->right = newChild;
min->child->left = newChild;
}
min->degree++;
newChild->marked = 0;
}
// Function to consolidate the heap by combining trees of the same degree
void consolidate(FibonacciHeap* heap) {
int maxDegree = heap->size / 2; // A loose upper bound on the degree
Node** degreeArray = (Node**)malloc(maxDegree * sizeof(Node*));
for (int i = 0; i < maxDegree; i++) {
degreeArray[i] = NULL;
}
Node* current = heap->min;
Node* start = heap->min;
do {
Node* next = current->right;
int degree = current->degree;
while (degreeArray[degree] != NULL) {
Node* other = degreeArray[degree];
if (current->key > other->key) {
Node* temp = current;
current = other;
other = temp;
}
link(current, other);
degreeArray[degree] = NULL;
degree++;
}
degreeArray[degree] = current;
current = next;
} while (current != start);
heap->min = NULL;
for (int i = 0; i < maxDegree; i++) {
if (degreeArray[i] != NULL) {
if (heap->min == NULL) {
heap->min = degreeArray[i];
} else {
if (degreeArray[i]->key < heap->min->key) {
heap->min = degreeArray[i];
}
}
}
}
free(degreeArray);
}
// Function to insert a new key into the Fibonacci Heap
void insert(FibonacciHeap* heap, int key) {
Node* newNode = createNode(key);
if (heap->min == NULL) {
heap->min = newNode;
} else {
newNode->right = heap->min;
newNode->left = heap->min->left;
heap->min->left->right = newNode;
heap->min->left = newNode;
if (key < heap->min->key) {
heap->min = newNode;
}
}
heap->size++;
}
// Function to extract the minimum key from the Fibonacci Heap
int extractMin(FibonacciHeap* heap) {
if (heap->min == NULL) {
return -1; // Indicating an empty heap
}
int minKey = heap->min->key;
Node* child = heap->min->child;
while (child != NULL) {
Node* nextChild = child->right;
child->left = heap->min->left;
child->right = heap->min->right;
heap->min->left->right = child;
heap->min->right->left = child;
child->parent = NULL;
child = nextChild;
}
heap->min->left->right = heap->min->right;
heap->min->right->left = heap->min->left;
Node* oldMin = heap->min;
if (oldMin == oldMin->right) {
heap->min = NULL;
} else {
heap->min = oldMin->right;
consolidate(heap);
}
free(oldMin);
heap->size--;
return minKey;
}
// Sample usage of the Fibonacci Heap
int main() {
FibonacciHeap* fibHeap = createFibonacciHeap();
insert(fibHeap, 10);
insert(fibHeap, 7);
insert(fibHeap, 5);
insert(fibHeap, 3);
printf("Extracted min: %d\n", extractMin(fibHeap));
printf("Extracted min: %d\n", extractMin(fibHeap));
printf("Extracted min: %d\n", extractMin(fibHeap));
free(fibHeap);
return 0;
}
#4 Fibonacci Heap implement in C++
Code -
C++ Programming
#include <iostream>
#include <vector>
#include <limits>
class FibonacciHeapNode {
public:
int key;
bool marked;
FibonacciHeapNode* parent;
FibonacciHeapNode* child;
FibonacciHeapNode* next;
FibonacciHeapNode* prev;
int degree;
FibonacciHeapNode(int key) : key(key), marked(false), parent(nullptr), child(nullptr), next(this), prev(this), degree(0) {}
};
class FibonacciHeap {
private:
FibonacciHeapNode* minNode;
int numNodes;
void link(FibonacciHeapNode* y, FibonacciHeapNode* x) {
// Remove y from the root list
y->prev->next = y->next;
y->next->prev = y->prev;
// Make y a child of x
y->parent = x;
if (x->child == nullptr) {
x->child = y;
y->next = y->prev = y;
} else {
y->next = x->child;
y->prev = x->child->prev;
x->child->prev->next = y;
x->child->prev = y;
}
// Increment the degree of x
x->degree++;
y->marked = false;
}
void consolidate() {
int maxDegree = static_cast < int>(log2(numNodes)) + 1;
std::vector<FibonacciHeapNode*> degreeArray(maxDegree, nullptr);
FibonacciHeapNode* current = minNode;
std::vector < FibonacciHeapNode*> roots;
do {
roots.push_back(current);
current = current->next;
} while (current != minNode);
for (FibonacciHeapNode* root : roots) {
int degree = root->degree;
while (degreeArray[degree] != nullptr) {
FibonacciHeapNode* other = degreeArray[degree];
if (root->key > other->key) {
std::swap(root, other);
}
link(other, root);
degreeArray[degree] = nullptr;
degree++;
}
degreeArray[degree] = root;
}
minNode = nullptr;
for (FibonacciHeapNode* node : degreeArray) {
if (node != nullptr) {
if (minNode == nullptr) {
minNode = node;
} else {
if (node->key < minNode->key) {
minNode = node;
}
}
}
}
}
public:
FibonacciHeap() : minNode(nullptr), numNodes(0) {}
bool isEmpty() const {
return minNode == nullptr;
}
void insert(int key) {
FibonacciHeapNode* node = new FibonacciHeapNode(key);
if (minNode == nullptr) {
minNode = node;
} else {
node->next = minNode;
node->prev = minNode->prev;
minNode->prev->next = node;
minNode->prev = node;
if (key < minNode->key) {
minNode = node;
}
}
numNodes++;
}
int getMin() const {
if (isEmpty()) {
throw std::out_of_range("Heap is empty");
}
return minNode->key;
}
int extractMin() {
if (isEmpty()) {
throw std::out_of_range("Heap is empty");
}
FibonacciHeapNode* min = minNode;
if (minNode->child != nullptr) {
FibonacciHeapNode* child = minNode->child;
do {
FibonacciHeapNode* nextChild = child->next;
child->prev = minNode->prev;
child->next = minNode->next;
minNode->prev->next = child;
minNode->next->prev = child;
child->parent = nullptr;
child = nextChild;
} while (child != minNode->child);
}
minNode->prev->next = minNode->next;
minNode->next->prev = minNode->prev;
if (minNode->next == minNode) {
minNode = nullptr;
} else {
minNode = minNode->next;
consolidate();
}
int minKey = min->key;
delete min;
numNodes--;
return minKey;
}
};
int main() {
FibonacciHeap fibHeap;
fibHeap.insert(3);
fibHeap.insert(1);
fibHeap.insert(4);
fibHeap.insert(6);
fibHeap.insert(8);
std::cout << "Min: " << fibHeap.getMin() << std::endl;
std::cout << "Extract Min: " << fibHeap.extractMin() << std::endl;
std::cout << "Min: " << fibHeap.getMin() << std::endl;
return 0;
}
Demonstration
Fibonacci Heap-DevsEnv