Fibonacci Heap

fibo_heap.h

#ifndef FIBONACCI_HEAP_H_
#define FIBONACCI_HEAP_H_

#include <memory>
#include <list>
#include <functional>
#include <algorithm>
#include <limits>
#include <cmath>
#include <vector>

template <class K, class V, class Compare = std::less<K>>  // K - key, V - data
class FibonacciHeap {
public:
    class Node;
    typedef std::shared_ptr<Node> nodeptr;
    class Node {
        friend class FibonacciHeap;
    public:
        Node(const K& key, const V& data) : m_parent(nullptr),
            m_left(nullptr),
            m_right(nullptr),
            m_child(nullptr),
            m_key(key),
            m_data(data),
            m_degree(0),
            m_mark(false) { }
        int degree() const { return m_degree; }
        const K& key() const { return m_key; }
        V& data() { return m_data; }
    private:
        nodeptr m_parent;
        nodeptr m_left;
        nodeptr m_right;
        nodeptr m_child;
        K m_key;
        V m_data;
        int m_degree;
        bool m_mark;
    };

    
    FibonacciHeap() : m_cmp(Compare()),
        m_min(nullptr), m_size(0) { }

    nodeptr min() const { return m_min; }

    nodeptr insert(const K& key, const V& value) {
        nodeptr res = std::make_shared<Node>(Node(key, value));
        if (m_min == nullptr) {
            res->m_right = res;
            res->m_left = res;
            m_min = res;
        } else {
            res->m_right = m_min;
            res->m_left = m_min->m_left;
            m_min->m_left->m_right = res;
            m_min->m_left = res;
            if (m_cmp(res->m_key, m_min->m_key)) {
                m_min = res;
            }
        }
        m_size++;
        return res;
    }

    FibonacciHeap& union_with(FibonacciHeap& other_heap) {
        FibonacciHeap res_heap;
        res_heap.m_min = this->m_min;
        append_second_list_to_first(res_heap.m_min, other_heap.m_min);
        if (this->m_min == nullptr
            || (other_heap.m_min != nullptr && m_cmp(other_heap.m_min->m_key, this->m_min->m_key))) {
            res_heap.m_min = other_heap.m_min;
        }
        res_heap.m_size = this->m_size + other_heap.m_size;
        return res_heap;
    }

    nodeptr extract_min() {
        nodeptr z = m_min;
        if (z != nullptr) {
            if (z->m_child != nullptr) {
                z->m_child->m_parent = nullptr;
                for (auto ptr = z->m_child->m_right; ptr != z->m_child; ptr = ptr->m_right) {
                    ptr->m_parent = nullptr;
                }
                append_second_list_to_first(m_min, z->m_child);
            }
            remove_from_heads_list(z);
            if (z == z->m_right) {
                m_min = nullptr;
            } else {
                m_min = z->m_right;
                consolidate();
            }
        }
        m_size--;
        return z;
    }

    bool decrease_key(nodeptr x, const K& new_key) {
        if (x == nullptr || m_cmp(x->m_key, new_key)) {
            return false;
        } else {
            x->m_key = new_key;
            nodeptr y = x->m_parent;
            if (y != nullptr && m_cmp(x->m_key, y->m_key)) {
                cut(x, y);
                cascading_cut(y);
            }
            if (m_cmp(x->m_key, m_min->m_key)) {
                m_min = x;
            }
            return true;
        }
    }

    void remove(nodeptr x) {
        decrease_key(x, std::numeric_limits<V>::min());
        extract_min();
        return;
    }

    bool empty() const { return (m_size == 0); }

private:
    Compare m_cmp;
    nodeptr m_min;
    int m_size;

    int max_degree() const {
        double log = std::log((double)m_size) / std::log(2);
        return (int)log + 1;
    }

    void append_second_list_to_first(nodeptr min1, nodeptr min2) {
        if (min2 == nullptr) {
            return;
        } else if (min1 == nullptr) {
            *min1 = *min2;
            return;
        } else {
            min1->m_left->m_right = min2->m_right;
            min2->m_right->m_left = min1->m_left;
            min1->m_left = min2;
            min2->m_right = min1;
            return;
        }
    }

    nodeptr remove_from_heads_list(nodeptr node) {
        if (node == nullptr) {
            return nullptr;
        } else if (node->m_right == node) {
            m_min = nullptr;
        } else {
            node->m_left->m_right = node->m_right;
            node->m_right->m_left = node->m_left;
        }
        return node;
    }

    nodeptr append_to_heads_list(nodeptr node) {
        node->m_parent = nullptr;
        if (m_min == nullptr) {
            m_min = node;
        } else {
            node->m_right = m_min;
            node->m_left = m_min->m_left;
            m_min->m_left->m_right = node;
            m_min->m_left = node;
        }
        return node;
    }

    void consolidate() {
        std::vector<nodeptr> A(max_degree() + 1, nullptr);
        nodeptr curr_ptr = m_min;
        if (curr_ptr->m_right == curr_ptr) {
            return;
        } else {
            do {
                nodeptr root1 = curr_ptr;
                int deg = curr_ptr->m_degree;
                while (A[deg] != nullptr) {
                    nodeptr root2 = A[deg];
                    if (m_cmp(root2->m_key, root1->m_key)) {
                        std::swap(root1, root2);
                        curr_ptr = root2;
                    }
                    if (root2 == m_min) {
                        m_min = root1;
                    }
                    heap_link_first_under_second(root2, root1); // Hang root2 under root1.
                    if (root1->m_right == root1) {
                        m_min = root1;
                        A[deg] = nullptr;
                    }
                    deg++;
                }
                A[deg] = root1;
                curr_ptr = curr_ptr->m_right;
            } while (curr_ptr != m_min);
            m_min = nullptr;
            for (auto it = A.begin(); it != A.end(); ++it) {
                auto ptr = *it;
                if (ptr != nullptr) {
                    if (m_min == nullptr) {
                        m_min = ptr;
                        m_min->m_left = m_min;
                        m_min->m_right = m_min;
                    } else {
                        m_min->m_left->m_right = ptr;
                        ptr->m_left = m_min->m_left;
                        ptr->m_right = m_min;
                        m_min->m_left = ptr;
                        if (m_cmp(ptr->key(), m_min->key())) {
                            m_min = ptr;
                        }
                    }
                }
            }
        }
    }

    // Hang y under x. This function is helper for extract_min function.
    void heap_link_first_under_second(nodeptr y, nodeptr x) {
        remove_from_heads_list(y);
        if (x->m_child == nullptr) {
            y->m_right = y->m_left = y;
        } else {
            y->m_right = x->m_child;
            y->m_left = x->m_child->m_left;
            x->m_child->m_left->m_right = y;
            x->m_child->m_left = y;
        }
        x->m_child = y;
        y->m_parent = x;
        x->m_degree++;
        y->m_mark = false;
        return;
    }

    void cut(nodeptr x, nodeptr y) {
        x->m_left->m_right = x->m_right;
        x->m_right->m_left = x->m_left;
        if (x == y->m_child) {
            if (x == x->m_right) {
                y->m_child = nullptr;
            } else {
                y->m_child = x->m_right;
            }
        }
        y->m_degree--;
        append_to_heads_list(x);
        x->m_parent = nullptr;
        x->m_mark = false;
        return;
    }

    void cascading_cut(nodeptr y) {
        nodeptr z = y->m_parent;
        if (z != nullptr) {
            if (y->m_mark == false) {
                y->m_mark = true;
            } else {
                cut(y, z);
                cascading_cut(z);
            }
        }
        return;
    }

};

#endif