Indexed Fibonacci heap implementation

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:

• Tips on improving performance

• Any bugs I haven't notice

• Any memory leaks

• 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
#include
#include
#include

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

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(
                                           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.)

StackExchange Code Review Q#138186, answer score: 2