Binomial Heap

bino_heap.h

#ifndef BINOMIAL_HEAP_H_
#define BINOMIAL_HEAP_H_

#include <memory>
#include <list>
#include <functional>
#include <algorithm>
#include <limits>

template <class K, class V, class Compare = std::less<K>> // K - key, V - additional data
class BinomialHeap {
public:
    class Node;
    typedef std::shared_ptr<Node> nodeptr;
    class Node {
        friend class BinomialHeap;
    public:
        Node(const K& key, const V& data) : parent_(nullptr),
                                            sibling_(nullptr),
                                            child_(nullptr),
                                            key_(key),
                                            data_(data),
                                            degree_(0) { }
        int degree() const { return degree_; }
        const K& key() const { return key_; }
        V& data() { return data_; }
    private:
        nodeptr parent_;
        nodeptr sibling_;
        nodeptr child_;
        K key_;
        V data_;
        int degree_;
    };

    BinomialHeap() : cmp_(Compare()) {
        heads_ = std::list<nodeptr>(1, nullptr);
    }

    nodeptr min() const {
        if (head_() == nullptr) {
            return nullptr;
        } else {
            nodeptr curr_min = head_();
            for (nodeptr ptr : heads_) {
                if (cmp_(ptr->key(), curr_min->key())) {
                    curr_min = ptr;
                }
            }
            return curr_min;
        }
    }

    BinomialHeap union_with(BinomialHeap& heap) {
        BinomialHeap res = merge_heaps(*this, heap);
        if (res.heads_.front() == nullptr) {
            return res;
        }
        nodeptr prev_x = nullptr;
        nodeptr x = res.heads_.front();
        nodeptr next_x = x->sibling_;
        while (next_x != nullptr) {
            if ((x->degree_ != next_x->degree_)
                || (next_x->sibling_ != nullptr && next_x->sibling_->degree_ == x->degree_)) {
                prev_x = x;
                x = next_x;
            } else if (cmp_(x->key_, next_x->key_)) {
                x->sibling_ = next_x->sibling_;
                link_trees(next_x, x);
            } else if (prev_x == nullptr) {
                res.heads_.front() = next_x;
            } else {
                prev_x->sibling_ = next_x;
                link_trees(x, next_x);
                x = next_x;
            }
            next_x = x->sibling_;
        }
        return res;
    }

    void insert(nodeptr node_ptr) {
        BinomialHeap one_node_heap;
        one_node_heap.heads_.front() = node_ptr;
        *this = this->union_with(one_node_heap);
        return;
    }

    nodeptr insert(const K& key, const V& data) {
        nodeptr node_ptr = std::make_shared<Node>(Node(key, data));
        insert(node_ptr);
        return node_ptr;
    }

    nodeptr extract_min() {
        if (heads_.front() == nullptr) {
            return nullptr;
        }
        Compare cmp;
        auto min_it = std::min(heads_.begin(), heads_.end(),
            [cmp](std::list<nodeptr>::iterator it1, std::list<nodeptr>::iterator it2) { return cmp((*it1)->key_, (*it2)->key_); });
        nodeptr min_ptr = *min_it;
        heads_.erase(min_it);
        std::list<nodeptr> childs_list;
        for (auto ptr = min_ptr->child_; ptr != nullptr; ptr = ptr->sibling_) {
            childs_list.push_front(ptr);
        }
        *this = this->union_with(BinomialHeap(childs_list));
        return min_ptr;
    }

    bool decrease_key(nodeptr node_ptr, K new_key) {
        if (cmp_(node_ptr->key_, new_key)) {
            return false;
        }
        node_ptr->key_ = new_key;
        nodeptr curr_ptr = node_ptr;
        nodeptr curr_parent = curr_ptr->parent_;
        while (curr_parent != nullptr && cmp_(curr_ptr->key_, curr_parent->key_)) {
            swap_adjacent_nodes(curr_ptr, curr_parent);
            curr_ptr = curr_parent;
            curr_parent = curr_ptr->parent_;
        }
        return true;
    }

    void remove(nodeptr node_ptr) {
        decrease_key(node_ptr, std::numeric_limits<K>::min());
        extract_min();
        return;
    }

    bool empty() const { return (heads_.front() == nullptr); }
private:
    BinomialHeap(const std::list<nodeptr>& heads) : cmp_(Compare()), heads_(heads) {
        if (heads_.size() == 0) {
            heads_.push_back(nullptr);
        }
    }
    Compare cmp_;
    std::list<nodeptr> heads_;
    nodeptr head_() const { return heads_.front(); }
    static void link_trees(nodeptr a, nodeptr b) {
        a->parent_ = b;
        a->sibling_ = b->child_;
        b->child_ = a;
        b->degree_++;
    }

    static BinomialHeap merge_heaps(BinomialHeap& h1, BinomialHeap& h2) {
        if (h1.heads_.front() == nullptr) {
            return BinomialHeap(h2.heads_);
        } else if (h2.heads_.front() == nullptr) {
            return BinomialHeap(h1.heads_);
        } else {
            std::list<nodeptr> new_heads;
            auto it1 = h1.heads_.begin();
            auto it2 = h2.heads_.begin();
            while (it1 != h1.heads_.end() && it2 != h2.heads_.end()) {
                if (h1.cmp_((*it1)->key_, (*it2)->key_)) {
                    new_heads.push_back(*it1);
                    ++it1;
                } else {
                    new_heads.push_back(*it2);
                    ++it2;
                }
            }
            return BinomialHeap(new_heads);
        }
    }

    void swap_adjacent_nodes(nodeptr a, nodeptr b) {
        Node x(*a);
        a->key_ = b->key_;
        a->data_ = b->data_;
        b->key_ = x.key_;
        b->data_ = x.data_;
        return;
    }
};

#endif