Indexed Fibonacci heap implementation

Question

I implemented two versions of a Fibonacci heap one using a unordered map (mapping keys to their nodes) so that the client can call decrease in \$O(1)\$ average and amortized time. The other one with a dynamic array of nodes and a maximum size for the same reason but in \$O(1)\$ amortize only. Both seem to be working fine.

I'm looking for:

1. Tips on improving performance
2. Any bugs I haven't notice
3. Any memory leaks
4. A better way for the client to call decreased key without having access to its internal representation

Implementation with unordered_map:

#ifndef FIB_HEAP_FIB_HEAP_H
#define FIB_HEAP_FIB_HEAP_H

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

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;
    }

};

#endif //FIB_HEAP_FIB_HEAP_H

Implementation with a dynamic array (this includes just the public methods and its members for brevity, since it's the only difference between the two implementations):

    static constexpr  double LOG_OF_GOLDEN = 0.4812118;

    unsigned max_size;
    node**   index_table;
    node*    min;
    unsigned N;
    unsigned root_size;
    Func     cmp;

public:

    index_fib_heap(unsigned pmax_size, Func pcmp)
        : max_size(pmax_size),
          index_table(new node*[pmax_size]()),
          min(nullptr),
          N(0),
          root_size(0), 
          cmp(pcmp) { }

    index_fib_heap(unsigned pmax_size) 
        : index_fib_heap(pmax_size, Func()) { }

     ~index_fib_heap() {
         auto n = min;
         for (auto i = 0u; i < root_size; ++i) {
             auto next = n->right;
             n->destroy();
             n = next;
         }
         delete[] index_table;
     }

    void pop() {
        auto min_node = remove_min();
        index_table[min_node->index] = nullptr;
        delete min_node;
    }

    const std::pair<unsigned, const P&> top() {
        return { min->index, min->prty };
    }

    template<typename PP>
    void insert(unsigned index, PP&& prty) {     
        check_index(index);
        auto &new_node = index_table[index];
        if (new_node != nullptr) {
            return;
        }
        new_node = new node(index, 
                   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(unsigned index, PP&& prty) {     
        check_index(index);
        auto node = index_table[index];
        if (node != nullptr) {
            decrease_priority(node, 
                std::forward<PP>(prty));
        }
    }

Answer 1

I can't tell you much, since if I were to implement a Fibonacci heap in C++, I would not do any better than you already did. Notwithstanding, you can squeeze a little bit more performance, in light of these results (with -O3 speed optimization) when loading 1e7 integers and then popping them all:

Fibonacci heap with array in 11523 milliseconds.
Fibonacci heap with storage in 9531 milliseconds.

What happens there? The first line is your mapped version of the data structure. The second line comes from a slight modification of your heap: instead of creating and deleting the degree array in consolidate, you allocate it only once as the class attribute. Along it, you cache the current capacity of the array; if it is too short, delete old array, allocate a larger one and cache the new capacity. (Don't forget to delete the array in you destructor.)

All in all, I had this in mind:

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;
}

Apart from that, your code looks nice and tidy. Good work!

(Full demonstration code is here.)

Answer 2

I haven't localized the issue completely yet, but if I use the unordered_map version of your code in the following example:

int main(int argc, const char * argv[]) {
    fib_heap<int, int> H;

    H.insert(19, 55);
    H.insert(96, 100);
    H.insert(1, 43);
    H.pop();

    H.insert(48, 99);
    H.insert(60, 55);
    H.insert(92, 70);
    H.pop();

    H.decrease(48, 27);

    std::cerr << H.top().first << '\n';
    return 0;
}

then the program terminates with Segmentation fault: 11. The same thing seems to happen with the fib_heap2 version posted by @coderodde.

Answer 3

As ewcz said, there is an error in the code here:

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;
}

The method remove_self does not update the parent's child property therefore when there is only one element, this is not removed. I check for this case after calling add_brother in line 4, but it should be check before. (In the particular case noted by ewcz at one point min == parent, creating a circular reference.)

Solution:

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;
}

---

Edit:

I found a second error in here (thanks to ewcz again). In the cut function n is added to the root therefore it's parent will be null after the call, and making n null for the next iteration:

void cascading_cut(node* n) {
    while (n->parent != nullptr && n->mark) {
        cut(n, n->parent);
        n = n->parent;
    }
    n->mark = n->mark || n->parent;
}

The solution is to save the parent before calling cut:

void cascading_cut(node* n) {
    while (n->parent != nullptr && n->mark) {
        node* p = n->parent;
        cut(n, p);
        n = p;
    }
    n->mark = n->mark || n->parent;
}