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:

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