Fibonacci Heap Data Structure Code Implementations
Production-ready Fibonacci Heap Data Structure data structure implementations in C++, Python, Java, and JavaScript on AntInLoop.
Study Fibonacci Heap Data Structure Guide ยท Launch Visualizer
CPP Implementation
#include <bits/stdc++.h>
using namespace std;
// Fibonacci Heap Node
struct Node {
int key;
int degree;
bool mark;
Node* parent;
Node* child;
Node* left;
Node* right;
Node(int val) {
key = val;
degree = 0;
mark = false;
parent = child = nullptr;
left = right = this;
}
};
// Fibonacci Heap
class FibonacciHeap {
private:
Node* minNode; // Pointer to minimum node
int n; // Number of nodes in heap
// Link two trees of same degree
void link(Node* y, Node* x) {
// Remove y from root list
y->left->right = y->right;
y->right->left = y->left;
// Make y child of x
y->parent = x;
if (x->child == nullptr) {
x->child = y;
y->left = y->right = y;
} else {
y->left = x->child;
y->right = x->child->right;
x->child->right->left = y;
x->child->right = y;
}
x->degree++;
y->mark = false;
}
// Consolidate trees after extractMin
void consolidate() {
int D = (int)(log2(n)) + 1;
vector<Node*> A(D, nullptr);
vector<Node*> rootList;
Node* x = minNode;
if (x != nullptr) {
do {
rootList.push_back(x);
x = x->right;
} while (x != minNode);
}
for (Node* w : rootList) {
x = w;
int d = x->degree;
while (A[d] != nullptr) {
Node* y = A[d];
if (x->key > y->key) swap(x, y);
link(y, x);
A[d] = nullptr;
d++;
}
A[d] = x;
}
minNode = nullptr;
for (Node* a : A) {
if (a != nullptr) {
if (minNode == nullptr) {
minNode = a;
a->left = a->right = a;
} else {
// Insert into root list
a->left = minNode;
a->right = minNode->right;
minNode->right->left = a;
minNode->right = a;
if (a->key < minNode->key) minNode = a;
}
}
}
}
public:
FibonacciHeap() {
minNode = nullptr;
n = 0;
}
// Insert a new key
Node* insert(int key) {
Node* x = new Node(key);
if (minNode == nullptr) {
minNode = x;
} else {
// Insert into root list
x->left = minNode;
x->right = minNode->right;
minNode->right->left = x;
minNode->right = x;
if (key < minNode->key) minNode = x;
}
n++;
return x;
}
// Get minimum key
int getMin() {
if (minNode == nullptr) throw runtime_error("Heap is empty");
return minNode->key;
}
// Union of two heaps
void merge(FibonacciHeap& other) {
if (other.minNode == nullptr) return;
if (minNode == nullptr) {
minNode = other.minNode;
n = other.n;
} else {
// Merge root lists
Node* temp = minNode->right;
minNode->right = other.minNode->right;
other.minNode->right->left = minNode;
other.minNode->right = temp;
temp->left = other.minNode;
if (other.minNode->key < minNode->key) minNode = other.minNode;
n += other.n;
}
other.minNode = nullptr;
other.n = 0;
}
// Extract minimum node
int extractMin() {
Node* z = minNode;
if (z != nullptr) {
// Add children to root list
if (z->child != nullptr) {
Node* c = z->child;
do {
Node* next = c->right;
// Insert c into root list
c->left = minNode;
c->right = minNode->right;
minNode->right->left = c;
minNode->right = c;
c->parent = nullptr;
c = next;
} while (c != z->child);
}
// Remove z from root list
z->left->right = z->right;
z->right->left = z->left;
if (z == z->right) {
minNode = nullptr;
} else {
minNode = z->right;
consolidate();
}
n--;
int val = z->key;
delete z;
return val;
}
throw runtime_error("Heap is empty");
}
// Decrease key
void decreaseKey(Node* x, int k) {
if (k > x->key) throw runtime_error("New key is greater than current key");
x->key = k;
Node* y = x->parent;
if (y != nullptr && x->key < y->key) {
// Cut and cascade cut
cut(x, y);
cascadingCut(y);
}
if (x->key < minNode->key) minNode = x;
}
private:
// Cut node from parent
void cut(Node* x, Node* y) {
if (x->right == x) {
y->child = nullptr;
} else {
x->right->left = x->left;
x->left->right = x->right;
if (y->child == x) y->child = x->right;
}
y->degree--;
// Add to root list
x->left = minNode;
x->right = minNode->right;
minNode->right->left = x;
minNode->right = x;
x->parent = nullptr;
x->mark = false;
}
// Cascading cut
void cascadingCut(Node* y) {
Node* z = y->parent;
if (z != nullptr) {
if (!y->mark) {
y->mark = true;
} else {
cut(y, z);
cascadingCut(z);
}
}
}
};
// Driver code
int main() {
FibonacciHeap heap;
auto* n1 = heap.insert(10);
auto* n2 = heap.insert(3);
auto* n3 = heap.insert(15);
auto* n4 = heap.insert(6);
cout << "Min: " << heap.getMin() << endl;
cout << "Extract Min: " << heap.extractMin() << endl;
cout << "New Min: " << heap.getMin() << endl;
heap.decreaseKey(n3, 2);
cout << "New Min after decreaseKey: " << heap.getMin() << endl;
return 0;
}