Fibonacci Heap Data Structure Data Structure
A Fibonacci Heap is a lazy mergeable priority queue using circular doubly linked root lists and cascading cuts to achieve O(1) amortized insert, merge, and decrease-key, and O(log n) amortized extract-min.
| Operation | Complexity |
|---|---|
| Access | O(1) min |
| Search | O(n) |
| Insertion | O(1) amortized |
| Deletion | O(log n) amortized |
| Space | O(n) |
Interactive Visualizer · C++ / Python / Java / JS Code
Fibonacci Heap Data Structure
A Fibonacci Heap (Fredman & Tarjan, 1984) is a lazy mergeable priority queue that defers all tree-linking work until extractMin. By keeping roots in a circular doubly linked list and performing cascading cuts on decreaseKey, it achieves $O(1)$ amortized insert, findMin, merge, and decreaseKey, and $O(\log n)$ amortized extractMin—giving Dijkstra's Algorithm and Prim's Algorithm their theoretically optimal $O(E + V \log V)$ bound!
At a Glance
| Operation | Binary Heap | Binomial Heap | Fibonacci Heap |
| :--- | :---: | :---: | :---: |
| findMin | $O(1)$ | $O(\log n)$ | $O(1)$ |
| insert | $O(\log n)$ | $O(1)$ amort. | $O(1)$ |
| merge | $O(n)$ | $O(\log n)$ | $O(1)$ |
| decreaseKey | $O(\log n)$ | $O(\log n)$ | $O(1)$ amortized |
| extractMin | $O(\log n)$ | $O(\log n)$ | $O(\log n)$ amortized |
---
Why It's Called a "Fibonacci" Heap
During decreaseKey, if a node loses one child, it gets marked = true; if it loses a second child, it is cut from its parent and moved to the root list (cascading cut). This guarantees that a subtree of degree $k$ has at least $F_{k+2} \ge \phi^k$ nodes (Fibonacci numbers!), bounding the maximum degree of any node by $O(\log_\phi n) = O(\log n)$.
---
Practice Problems
Easy
1. Core Fibonacci Heap (insert, merge, extractMin, decreaseKey)
Implement a Fibonacci Heap demonstrating $O(1)$ insert/merge/decreaseKey with cascading cuts and extractMin consolidation.
Approach: Circular doubly linked root list + degree-indexed consolidation table in extractMin + cut/cascadingCut in decreaseKey.
<details>
<summary>Show C++ Solution</summary>
#include <cmath>
#include <iostream>
#include <utility>
#include <vector>
struct FibNode {
int key, deg = 0;
bool marked = false;
FibNode *parent = nullptr, *child = nullptr, *left, *right;
explicit FibNode(int k) : key(k), left(this), right(this) {}
};
class FibHeap {
FibNode* minNode = nullptr;
int count = 0;
static void addToList(FibNode* a, FibNode* b) {
b->left = a;
b->right = a->right;
a->right->left = b;
a->right = b;
}
static void removeFromList(FibNode* x) {
x->left->right = x->right;
x->right->left = x->left;
x->left = x->right = x;
}
void link(FibNode* y, FibNode* x) {
removeFromList(y);
y->parent = x;
if (!x->child) x->child = y;
else addToList(x->child, y);
++x->deg;
y->marked = false;
}
void consolidate() {
int maxDeg = static_cast<int>(std::log2(count + 1)) * 2 + 4;
std::vector<FibNode*> table(maxDeg, nullptr);
std::vector<FibNode*> roots;
FibNode* cur = minNode;
do { roots.push_back(cur); cur = cur->right; } while (cur != minNode);
for (FibNode* w : roots) {
FibNode* x = w;
int d = x->deg;
while (table[d]) {
FibNode* y = table[d];
if (x->key > y->key) std::swap(x, y);
link(y, x);
table[d] = nullptr;
++d;
}
table[d] = x;
}
minNode = nullptr;
for (FibNode* r : table) {
if (!r) continue;
r->left = r->right = r;
if (!minNode) minNode = r;
else {
addToList(minNode, r);
if (r->key < minNode->key) minNode = r;
}
}
}
void cut(FibNode* x, FibNode* y) {
if (x->right == x) y->child = nullptr;
else { if (y->child == x) y->child = x->right; removeFromList(x); }
--y->deg;
x->parent = nullptr;
x->marked = false;
addToList(minNode, x);
}
void cascadingCut(FibNode* y) {
FibNode* z = y->parent;
if (z) {
if (!y->marked) y->marked = true;
else { cut(y, z); cascadingCut(z); }
}
}
public:
FibNode* insert(int key) {
auto* n = new FibNode(key);
if (!minNode) minNode = n;
else { addToList(minNode, n); if (key < minNode->key) minNode = n; }
++count;
return n;
}
void decreaseKey(FibNode* x, int newKey) {
x->key = newKey;
FibNode* y = x->parent;
if (y && x->key < y->key) { cut(x, y); cascadingCut(y); }
if (x->key < minNode->key) minNode = x;
}
int extractMin() {
FibNode* z = minNode;
if (z->child) {
std::vector<FibNode*> kids;
FibNode* c = z->child;
do { kids.push_back(c); c = c->right; } while (c != z->child);
for (FibNode* k : kids) { k->parent = nullptr; addToList(minNode, k); }
}
int res = z->key;
if (z == z->right) { minNode = nullptr; }
else { minNode = z->right; removeFromList(z); consolidate(); }
delete z;
--count;
return res;
}
bool empty() const { return count == 0; }
};
int main() {
FibHeap fh;
fh.insert(10);
auto* n20 = fh.insert(20);
fh.insert(5);
fh.decreaseKey(n20, 3);
while (!fh.empty()) std::cout << fh.extractMin() << " ";
std::cout << "\n"; // 3 5 10
return 0;
}
</details>
---
Related Structures & Algorithms
- Binary Heap — simpler and usually faster in practice due to cache locality.
- Binomial Heap — eager sibling of Fibonacci Heap.
- Dijkstra's Algorithm — achieves $O(E + V \log V)$ with a Fibonacci Heap.