CodeReview Fibonacci heap performance demonstration

main.cpp

#include <iostream>

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

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)) {
            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) {
        min->add_brother(child->remove_self());
        child->mark = false;
        --parent->degree;
        if (parent->degree == 0) {
            parent->childs = nullptr;
        }
        else if (parent->childs == child) {
            parent->childs = child->right;
        }
        ++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;
    }
    
};

template<typename K, typename P, typename  Func = std::less<P>>
class fib_heap2 {
    
    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;
        if (bound > degree_array_length)
        {
            delete[] degree_array;
            degree_array = new node*[bound]();
            degree_array_length = bound;
        }
        else
        {
            std::memset(degree_array, 0, bound * sizeof(node*));
        }
        
        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]);
            }
        }
        ++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)) {
            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) {
        min->add_brother(child->remove_self());
        child->mark = false;
        --parent->degree;
        if (parent->degree == 0) {
            parent->childs = nullptr;
        }
        else if (parent->childs == child) {
            parent->childs = child->right;
        }
        ++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** degree_array = new node*[10];
    size_t degree_array_length = 10;
    
    node*    min;
    unsigned N;
    unsigned root_size;
    Func     cmp;
    
public:
    
    fib_heap2()
    : fib_heap2(Func()){ }
    
    fib_heap2(Func pcmp) :
    min(nullptr),
    N(0),
    root_size(0),
    cmp(pcmp) { }
    
    ~fib_heap2() {
        auto n = min;
        for (auto i = 0u; i < root_size; ++i) {
            auto next = n->right;
            n->destroy();
            n = next;
        }
        delete[] degree_array;
    }
    
    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;
    }
    
};

class CurrentTime {
    std::chrono::high_resolution_clock m_clock;
    
public:
    uint64_t milliseconds()
    {
        return std::chrono::duration_cast<std::chrono::milliseconds>
        (m_clock.now().time_since_epoch()).count();
    }
};

int main(int argc, const char * argv[]) {
    fib_heap<int, int> heap1;
    fib_heap2<int, int> heap2;
    
    CurrentTime ct;
    
    auto start = ct.milliseconds();
    
    for (int i = 0; i < 10 * 1000 * 1000; ++i)
    {
        heap1.insert(i, 10 * 1000 * 1000 - i);
    }
    
    while (heap1.size() > 0)
    {
        heap1.pop();
    }
    
    auto end = ct.milliseconds();
    
    std::cout << "Fibonacci heap with array in " << (end - start) << " milliseconds." << std::endl;

    start = ct.milliseconds();
    
    for (int i = 0; i < 10 * 1000 * 1000; ++i)
    {
        heap2.insert(i, 10 * 1000 * 1000 - i);
    }
    
    while (heap2.size() > 0)
    {
        heap2.pop();
    }
    
    end = ct.milliseconds();
    
    std::cout << "Fibonacci heap with storage in " << (end - start) << " milliseconds." << std::endl;
    return 0;
}