FibonacciHeap

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

template <class T>
class Node
{
private:
    T data;
    Node<T>* left;
    Node<T>* right;
    Node<T>* parent;
    Node<T>* child;
    bool marked;
    int degree;

    Node<T>()
        : data(T())
        , left(this)
        , right(this)
        , parent(nullptr)
        , child(nullptr)
        , marked(false)
        , degree(0)
    {}

    Node<T>(const T& n)
        : data(n)
        , left(this)
        , right(this)
        , parent(nullptr)
        , child(nullptr)
        , marked(false)
        , degree(0)
    {}

    T getData() const
    {
        return data;
    }

    void setData(const T& n)
    {
        data = n;
    }

    ~Node<T>()
    {
        delete left;
        delete right;
        delete parent;
        delete child;
        left = right = parent = child = nullptr;
    }

    template <class T>
    friend class FibonacciHeap;

};

template <class T>
class FibonacciHeap
{
private:

    Node<T>* root;

    int size;


    void inserting(Node<T>* _root, Node<T>* x)
    {
        x->left = _root;
        x->right = _root->right;
        _root->right->left = x;
        _root->right = x;
    }

    void take_out(Node<T>* x)
    {
        x->left->right = x->right;
        x->right->left = x->left;
    }

    void link(Node<T>* parent, Node<T>* child)
    {

        if (!parent || !child) throw "Nullptr";

        child->parent = parent;
        take_out(child);

        if (!parent->child)
        {
            parent->child = child;
            child->left = child;
            child->right = child;
        }
        else
            inserting(parent->child, child);

        parent->degree++;
        parent->marked = false;

    }

    void consolidate()
    {
        vector<Node<T>*> degrees(int(log2(size)) + 1, nullptr);
        vector<Node<T>*> elements;


        Node<T>* cur = root;
        do
        {
            elements.push_back(cur);
            cur = cur->right;
        } while (cur != root);


        for (auto it : elements)
        {
            int curDegree = it->degree;

            while (degrees[curDegree])
            {
                Node<T>* buff = degrees[curDegree];

                if (it->data > buff->data)
                    swap(it, buff);

                link(it, buff);
                degrees[curDegree] = nullptr;
                curDegree++;
            }
            degrees[curDegree] = it;
        }

        root = nullptr;
        for (auto it : degrees)
        {
            if (it)
            {
                if (!root) root = it;

                take_out(it);
                inserting(root, it);

                if (root->data > it->data) root = it;

            }
        }
    }

    void cut(Node<T>* parent, Node<T>* child)
    {
        take_out(child);

        if (parent->child == child)
        {
            if (child->right == child)
                parent->child = nullptr;
            else
                parent->child = child->right;
        }

        child->parent = nullptr;
        child->marked = false;
        inserting(root, child);

        if (child->data < root->data)
            root = child;

        parent->degree--;
    }

    void cascadingCut(Node<T>* x)
    {
        if (x->parent != nullptr)
        {
            if (!x->marked)
                x->marked = true;
            else
            {
                cut(x->parent, x);
                cascadingCut(x->parent);
            }
        }


    }


public:

    FibonacciHeap()
        : root(nullptr)
        , size(0)
    {}

    T getMin() const
    {
        return root->data;
    }

    int count() const
    {
        return size;
    }

    void add(const T& elem)
    {
        Node<T>* newNode = new Node<T>(elem);

        if (!root)
            root = newNode;
        else
        {
            inserting(root, newNode);

            if (root->data > newNode->data)
                root = newNode;
        }
        size++;
    }


    FibonacciHeap<T> merge(FibonacciHeap<T>& H)
    {
        if (!H.root) throw "Nullptr";
        else if (!root)
            root = H.root;
        else
        {
            inserting(root, H.root);
            root = (root->data < H.root->data ? root : H.root);
        }

        size += H.size;
        H.size = 0;
        H.root = nullptr;

        return *this;
    }

    Node<T>* remove_min()
    {
        if (!root) throw "Heap is empty";

        if (root->child)
        {
            Node<T>* cur = root->child;

            do
            {
                cur = cur->right;
                inserting(root, cur);
                cur->parent = nullptr;

            } while (cur != root->child);
        }

        take_out(root);

        if (root == root->right)
            root = nullptr;
        else
        {
            root = root->right;
            consolidate();
        }
        return root;
    }


    void decrease_key(Node<T>* x, const T& k)
    {
        if (k >= x->data)
        {
            cout << "New data is greater then current\n";
            return;
        }

        x->data = k;
        if (x->parent && x->data < x->parent->data)
        {
            cur(x->parent, x);
            cascadingCut(x->parent);
        }
    }

 void destroyNodes(Node<T>* node)
   {
        if (node)
       {
            Node<T>* cur = node;
            do
           {
                Node<T>* next = cur->right;
                destroyNodes(cur->child);
                delete cur;
                cur = next;
            } while (cur != node);
        }
    }

~FibonacciHeap()
{
   destroyNodes(root);
}

};

int main()
{
    FibonacciHeap<int> A;

    A.add(10);
    A.add(11);
    A.add(15);
    A.add(-1);

    cout << "Minimum: " << A.getMin() << '\n';
    cout << "Size of Heap: " << A.count() << '\n';

    cout << "\nRemove min:\n";
    A.remove_min();
    cout << "Current min: " << A.getMin() << '\n';

    cout << "\nMerge of Heaps:\n";

    FibonacciHeap<int> B;
    B.add(40);
    B.add(-199);
    B.add(14);
    B.add(0);

    cout << "Heap B min: " << B.getMin() << '\n';
    cout << "Heap A min: " << A.getMin() << '\n';
    cout << "Connect Heap A and Heap B:\n";
    A.merge(B);
    cout << "Current min: " << A.getMin() << '\n';


    cout << "\nDecrease min key\n";



    return 0;
}