FibbHeap.cpp

#include <iostream>
#include <cmath>

using namespace std;

/**
 * @brief Fibonacci min heap.
 */
template <typename T>
class FibbHeap
{
private:
    struct node
    {
        node *parent, *child, *left, *right;
        T data;
        int degree;
        bool isBlack;
        node(T data) : data(data), isBlack(false), degree(0), parent(nullptr), child(nullptr), left(this), right(this)
        {
            left = this;
            right = this;
        };
        /**
         * @brief Insert this node as left sibbling of given node.
         */
        inline void push_left_of(node *p)
        {
            p->left->right = this;
            this->right = p;
            this->left = p->left;
            p->left = this;
        }
        /**
         * @brief Insert this node as right sibbling of given node.
         */
        inline void push_right_of(node *p)
        {
            p->right->left = this;
            right = p->right;
            left = p;
            p->right = this;
        }
        /**
         * @brief Disconnect this node from its sibbling chain and set its left and right to itself.
         */
        inline void pop_sibblings()
        {
            left->right = right;
            right->left = left;
            left = right = this;
        }
    };
    node *min_root = nullptr;
    int n_nodes = 0;

    /**
     * @brief Compresses all nodes in top level list such that they create a fibonacci heap.
     */
    void consolidate()
    {
        int max_degree = (log(n_nodes + 1) / log(2));
        node *A[max_degree + 1] = {nullptr};
        node *x = min_root;
        // Count top level list
        int N = 1;
        for(x=min_root->right;x!=min_root;x=x->right)++N;
        // Loop over top level list
        node *ptr = min_root;
        // cout <<"N: "<<N<<endl;
        for(;N>0;--N)
        {
            int d = ptr->degree;
            ptr = ptr->right;
            x = ptr->left;
            x->pop_sibblings();
            x->parent = nullptr;
            while (A[d] != nullptr)
            {
                node *y = A[d];
                if (x->data > y->data)
                    std::swap(x, y);
                // Make y child of x
                {
                    y->pop_sibblings();
                    y->parent = x;
                    if (x->child == nullptr)
                        x->child = y;
                    y->push_left_of(x->child);
                    if (y->data < x->child->data)
                        x->child = y;
                    ++(x->degree);
                }
                A[d] = nullptr;
                ++d;
            }
            A[d] = x;
        };
        min_root = nullptr;
        for (int j = 0; j <= max_degree; j++)
        {
            if (A[j] != nullptr)
            {
                // Make A[j] independent node
                A[j]->left = A[j]->right = A[j];
                A[j]->parent = nullptr;
                if (min_root == nullptr)
                    min_root = A[j];
                else
                {
                    A[j]->push_left_of(min_root);
                    if (A[j]->data < min_root->data)
                        min_root = A[j];
                }
            }
        }
    }

public:
    void insert(T data)
    {
        auto n = new node(data);
        ++n_nodes;
        if (min_root == nullptr)
        {
            min_root = n;
            return;
        }
        else
        {
            // Insert at left of min_root
            n->push_left_of(min_root);
            // Update min node
            if (data < min_root->data)
            {
                min_root = n;
            }
        }
    }

    /**
     * @brief Extracts the min node in heap. This node is removed from heap.
     *
     * @return T The smallest node removed from heap.
     */
    T pop()
    {
        if (min_root == nullptr)
            throw "Can't pop from empty heap.";
        // cout<<"MIN root: "<<(min_root->data)<<endl;
        if (min_root->child != nullptr)
        {
            // Insert all min_root children to top level
            node *x = min_root->child;
            node *ptr;
            for(int i=0;i<min_root->degree;++i)
            {
                ptr = x->right;
                x->push_left_of(min_root);
                // cout<<"leftpush: "<<(x->data)<<endl;
                x->parent = nullptr;
                x = ptr;
            }
        }
        // find newmin
        node *newmin = min_root->right;
        // Remove min_root
        min_root->pop_sibblings();
        T ret = min_root->data;
        delete min_root;
        --n_nodes;
        if (n_nodes == 0)
        {
            min_root = nullptr;
        }
        else
        {
            min_root = newmin;
            consolidate();
        }
        return ret;
    }

    // Function to display the heap
    void display()
    {
        display(min_root, 4);
        cout << endl;
    }
    void display(node *ptr, int depth)
    {
        if (ptr != nullptr && depth > 0)
        {
            cout << "[";
            node *p = ptr;
            do
            {
                if (p == nullptr)
                    break;
                cout << p->data;
                display(p->child, depth - 1);
                cout << "-->";
                p = p->right;
            } while (ptr != p);
            cout << "]";
        }
    }
};

int main()
{
    cout << "hi" << endl;
    FibbHeap<int> h;
    for (int i = 0; i < 100; ++i)
        h.insert(i);
    h.display();
    for (int i = 0; i < 100; ++i)
    {
        cout << i << " - Pop: " << h.pop() << endl;
        h.display();
    }
    return 0;
}