Skip to content

Instantly share code, notes, and snippets.

@persiyanov
Created April 19, 2015 21:06
Show Gist options
  • Save persiyanov/0d5f82f243280b90ff60 to your computer and use it in GitHub Desktop.
Save persiyanov/0d5f82f243280b90ff60 to your computer and use it in GitHub Desktop.
Binomial Heap
#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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment