AntInLoop

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.

OperationComplexity
AccessO(1) min
SearchO(n)
InsertionO(1) amortized
DeletionO(log n) amortized
SpaceO(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