AntInLoop

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;
}