CodeReview - Fibonacci heap

sample.cc

#include <iostream>

#include <algorithm>
#include <stdexcept>
#include <functional>
#include <unordered_map>
#include <vector>
#include <random>

template<typename K, typename P, typename  Func = std::less<P>>
class fib_heap {
    
    struct node {
        
        K key;
        P prty;
        unsigned degree = 0;
        bool mark       = false;
        
        node* parent = nullptr;
        node* childs = nullptr;
        node* left   = nullptr;
        node* right  = nullptr;
        
        node(const K& pkey, const P& priority)
        : key(pkey),
        prty(priority) { }
        
        node(K&& pkey, const P& priority)
        : key(std::move(pkey)),
        prty(priority) { }
        
        node(const K& pkey, P&& priority)
        : key(pkey),
        prty(std::move(priority)) { }
        
        node(K&& pkey, P&& priority)
        : key(std::move(pkey)),
        prty(std::move(priority)) { }
        
        node* add_brother(node* n) {
            n->parent   = parent;
            n->left     = this;
            n->right    = right;
            right->left = n;
            right       = n;
            return this;
        }
        node* remove_self() {
            left->right = right;
            right->left = left;
            return this;
        }
        
        node* add_child(node* n) {
            if (childs == nullptr) {
                childs    = n->to_single_list();
                n->parent = this;
            }
            else {
                childs->add_brother(n);
            }
            n->mark = false;
            ++degree;
            return this;
        }
        
        node* to_single_list() {
            left  = this;
            right = this;
            return this;
        }
        
        void destroy() {
            auto n = childs;
            for (auto i = 0u; i < degree; ++i) {
                auto next = n->right;
                n->destroy();
                n = next;
            }
            delete this;
        }
    };
    
    void consolidate() {
        unsigned bound = static_cast<unsigned>(
                                               std::log(N) / LOG_OF_GOLDEN) + 1;
        auto degree_array = new node*[bound]();
        
        for (auto n = min; root_size > 0; --root_size) {
            auto parent = n;
            auto d      = parent->degree;
            n           = n->right;
            
            while (degree_array[d] != nullptr) {
                auto child = degree_array[d];
                if (cmp(child->prty, parent->prty)) {
                    std::swap(child, parent);
                }
                parent->add_child(child->remove_self());
                degree_array[d++] = nullptr;
            }
            degree_array[d] = parent;
        }
        
        auto d = 0u;
        while (degree_array[d++] == nullptr);
        
        min = degree_array[d - 1]->to_single_list();
        for (; d < bound; ++d) {
            if (degree_array[d] != nullptr) {
                add_to_root(degree_array[d]);
            }
        }
        delete [] degree_array;
        ++root_size;
    }
    
    node* remove_min() {
        if (empty()) {
            throw std::underflow_error("underflow");
        }
        
        auto deleted = min;
        add_childs_to_root(deleted);
        deleted->remove_self();
        --root_size;
        
        if (deleted == deleted->right) {
            min = nullptr;
        }
        else {
            min = min->right;
            consolidate();
        }
        --N;
        return deleted;
    }
    
    void add_to_root(node* n) {
        min->add_brother(n);
        if (cmp(n->prty, min->prty)) {
            min = n;
        }
        ++root_size;
    }
    
    void add_childs_to_root(node* n) {
        auto c = n->childs;
        auto d = n->degree;
        for (auto i = 0u; i < d; ++i) {
            auto next = c->right;
            add_to_root(c);
            c = next;
        }
    }
    
    template<typename PP>
    void decrease_priority(node *n, PP&& new_p) {
        if (cmp(n->prty, new_p)) {
            return; //throw std::runtime_error("key is greater");
        }
        
        n->prty = std::forward<PP>(new_p);
        auto p  = n->parent;
        
        if (p != nullptr
            && cmp(n->prty, p->prty)) {
            cut(n, p);
            cascading_cut(p);
        }
        if (cmp(n->prty, min->prty)) {
            min = n;
        }
    }
    
    void cut(node* child, node* parent) {
        child->remove_self();
        child->mark = false;
        --parent->degree;
        if (parent->degree == 0) {
            parent->childs = nullptr;
        }
        else if (parent->childs == child) {
            parent->childs = child->right;
        }
        min->add_brother(child);
        ++root_size;
    }
    
    void cascading_cut(node* n) {
        while (n->parent != nullptr && n->mark) {
            cut(n, n->parent);
            n = n->parent;
        }
        n->mark = n->mark || n->parent;
    }
    
    static constexpr  double     LOG_OF_GOLDEN = 0.4812118;
    std::unordered_map<K, node*> map_to_ptr;
    
    node*    min;
    unsigned N;
    unsigned root_size;
    Func     cmp;
    
public:
    
    fib_heap()
    : fib_heap(Func()){ }
    
    fib_heap(Func pcmp) :
    min(nullptr),
    N(0),
    root_size(0),
    cmp(pcmp) { }
    
    ~fib_heap() {
        auto n = min;
        for (auto i = 0u; i < root_size; ++i) {
            auto next = n->right;
            n->destroy();
            n = next;
        }
    }
    
    void pop() {
        auto min_node = remove_min();
        map_to_ptr.erase(min_node->key);
        delete min_node;
    }
    
    const std::pair<const K&, const P&> top() {
        return { min->key, min->prty };
    }
    
    template<typename KK, typename PP>
    void insert(KK&& key, PP&& prty) {
        auto &new_node = map_to_ptr[key];
        if (new_node != nullptr) {
            return;
        }
        new_node = new node(std::forward<KK>(key),
                            std::forward<PP>(prty));
        if (min == nullptr) {
            min = new_node->to_single_list();
            ++root_size;
        }
        else {
            add_to_root(new_node);
        }
        ++N;
    }
    
    template<typename PP>
    void decrease(const K& key, PP&& prty) {
        auto itr = map_to_ptr.find(key);
        if (itr != map_to_ptr.end()) {
            decrease_priority(itr->second,
                              std::forward<PP>(prty));
        }
    }
    
    bool empty() {
        return min == nullptr;
    }
    
    unsigned size() {
        return N;
    }
    
};

int main(int argc, const char * argv[]) {

    fib_heap<int, int> H;
    
H.insert(93, 45);
H.decrease(44, 100);
H.insert(38, 69);
H.insert(96, 17);
H.pop();
H.insert(90, 34);
H.decrease(43, 83);
H.insert(25, 90);
H.pop();
H.insert(60, 93);
H.decrease(8, 46);
H.insert(44, 9);
H.pop();
H.insert(59, 16);
H.pop();
H.insert(70, 77);
H.decrease(71, 67);
H.insert(78, 51);
H.pop();
H.insert(12, 19);
H.insert(40, 90);
H.insert(49, 49);
H.insert(74, 90);
H.decrease(72, 2);
H.insert(73, 85);
H.pop();
H.insert(4, 44);
H.pop();
H.insert(19, 10);
H.insert(64, 9);
H.decrease(25, 72);
H.insert(90, 18);
H.insert(55, 40);
H.pop();
H.insert(70, 52);
H.pop();
H.insert(87, 34);
H.pop();
H.insert(85, 9);
H.pop();
H.insert(68, 83);
H.pop();
H.insert(63, 100);
H.decrease(10, 40);
H.insert(66, 87);
H.decrease(61, 47);
H.insert(28, 75);
H.insert(5, 11);
H.pop();
H.insert(75, 4);
H.insert(22, 40);
H.decrease(11, 30);
H.insert(6, 32);
H.insert(23, 41);
H.decrease(65, 69);
H.insert(2, 36);
H.pop();
H.insert(84, 96);
H.decrease(31, 54);
H.insert(67, 59);
H.insert(66, 12);
H.pop();
H.insert(90, 35);
H.insert(26, 100);
H.decrease(63, 78);
H.insert(23, 73);
H.decrease(9, 53);
H.insert(3, 98);
H.pop();
H.insert(3, 73);
H.pop();
H.insert(60, 94);
H.pop();
H.insert(51, 3);
H.pop();
H.insert(45, 67);
H.insert(74, 49);
H.pop();
H.insert(33, 30);
H.pop();
H.insert(83, 9);
H.pop();
H.insert(64, 43);
H.pop();
H.insert(52, 62);
H.decrease(53, 37);
H.insert(88, 50);
H.pop();
H.insert(37, 76);
H.insert(8, 92);
H.pop();
H.insert(92, 2);
H.pop();
H.insert(44, 9);
H.decrease(73, 21);
H.insert(78, 49);
H.pop();
H.insert(15, 56);
H.pop();
H.insert(17, 21);
H.decrease(58, 3);
H.insert(86, 55);
H.pop();
H.insert(4, 92);
H.decrease(68, 49);
H.insert(61, 21);
H.decrease(33, 77);
H.insert(98, 58);
H.decrease(29, 35);
H.insert(29, 34);
H.decrease(83, 32);
H.insert(85, 100);
H.pop();
H.insert(59, 40);
H.insert(92, 39);
H.pop();
H.insert(50, 78);
H.decrease(34, 78);
H.insert(10, 52);
H.pop();
H.insert(87, 13);
H.pop();
H.insert(92, 97);
H.pop();
H.insert(62, 38);
H.decrease(80, 3);
H.insert(72, 48);
H.pop();
H.insert(41, 46);
H.decrease(79, 26);
H.insert(27, 76);
H.insert(55, 35);
H.insert(100, 55);
H.pop();
H.insert(38, 88);
H.pop();
H.insert(68, 79);
H.decrease(86, 92);
H.insert(74, 33);
H.decrease(82, 25);
H.insert(94, 24);
H.decrease(12, 87);
H.insert(79, 64);
H.insert(69, 90);
H.insert(3, 48);
H.insert(41, 53);
H.decrease(85, 33);
H.insert(38, 42);
H.pop();
H.insert(65, 46);
H.insert(37, 90);
H.insert(44, 99);
H.pop();
H.insert(73, 60);
H.pop();
H.insert(33, 99);
H.decrease(78, 45);
H.insert(66, 24);
H.pop();
H.insert(59, 89);
H.insert(97, 60);
H.decrease(32, 10);
H.insert(9, 47);
H.pop();
H.insert(48, 56);
H.insert(28, 16);
H.decrease(56, 77);
H.insert(49, 54);
H.insert(57, 44);
H.insert(30, 16);
H.insert(50, 88);
H.decrease(15, 30);
H.insert(38, 23);
H.insert(66, 66);
H.insert(67, 62);
H.pop();
H.insert(1, 20);
H.decrease(96, 60);
H.insert(99, 11);
H.decrease(94, 62);
H.insert(91, 50);
H.pop();
H.insert(52, 44);
H.insert(9, 52);
H.pop();
H.insert(32, 95);
H.pop();
H.insert(13, 97);
H.decrease(4, 18);
H.insert(22, 60);
H.insert(12, 48);
H.insert(14, 20);
H.decrease(28, 84);
H.insert(89, 66);
H.pop();
H.insert(37, 55);
H.pop();
H.insert(82, 55);
H.pop();
H.insert(96, 79);
H.decrease(72, 53);
H.insert(6, 96);
H.decrease(94, 70);
H.insert(85, 14);
H.insert(39, 11);
H.pop();
H.insert(44, 49);
H.pop();
H.insert(67, 53);
H.insert(11, 48);
H.pop();
H.insert(50, 21);
H.decrease(43, 92);
H.insert(96, 24);
H.decrease(19, 58);
H.insert(92, 43);
H.decrease(84, 2);

    std::cerr << H.top().first << std::endl;

    return 0;
}