Skip to content

Instantly share code, notes, and snippets.

@czew czew/sample.cc
Created Apr 18, 2017

Embed
What would you like to do?
CodeReview - Fibonacci heap
#include <iostream>
#include <algorithm>
#include <stdexcept>
#include <functional>
#include <unordered_map>
#include <vector>
#include <random>
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)) {
return; //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) {
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;
}
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;
}
};
int main(int argc, const char * argv[]) {
fib_heap<int, int> H;
H.insert(93, 45);
H.decrease(44, 100);
H.insert(38, 69);
H.insert(96, 17);
H.pop();
H.insert(90, 34);
H.decrease(43, 83);
H.insert(25, 90);
H.pop();
H.insert(60, 93);
H.decrease(8, 46);
H.insert(44, 9);
H.pop();
H.insert(59, 16);
H.pop();
H.insert(70, 77);
H.decrease(71, 67);
H.insert(78, 51);
H.pop();
H.insert(12, 19);
H.insert(40, 90);
H.insert(49, 49);
H.insert(74, 90);
H.decrease(72, 2);
H.insert(73, 85);
H.pop();
H.insert(4, 44);
H.pop();
H.insert(19, 10);
H.insert(64, 9);
H.decrease(25, 72);
H.insert(90, 18);
H.insert(55, 40);
H.pop();
H.insert(70, 52);
H.pop();
H.insert(87, 34);
H.pop();
H.insert(85, 9);
H.pop();
H.insert(68, 83);
H.pop();
H.insert(63, 100);
H.decrease(10, 40);
H.insert(66, 87);
H.decrease(61, 47);
H.insert(28, 75);
H.insert(5, 11);
H.pop();
H.insert(75, 4);
H.insert(22, 40);
H.decrease(11, 30);
H.insert(6, 32);
H.insert(23, 41);
H.decrease(65, 69);
H.insert(2, 36);
H.pop();
H.insert(84, 96);
H.decrease(31, 54);
H.insert(67, 59);
H.insert(66, 12);
H.pop();
H.insert(90, 35);
H.insert(26, 100);
H.decrease(63, 78);
H.insert(23, 73);
H.decrease(9, 53);
H.insert(3, 98);
H.pop();
H.insert(3, 73);
H.pop();
H.insert(60, 94);
H.pop();
H.insert(51, 3);
H.pop();
H.insert(45, 67);
H.insert(74, 49);
H.pop();
H.insert(33, 30);
H.pop();
H.insert(83, 9);
H.pop();
H.insert(64, 43);
H.pop();
H.insert(52, 62);
H.decrease(53, 37);
H.insert(88, 50);
H.pop();
H.insert(37, 76);
H.insert(8, 92);
H.pop();
H.insert(92, 2);
H.pop();
H.insert(44, 9);
H.decrease(73, 21);
H.insert(78, 49);
H.pop();
H.insert(15, 56);
H.pop();
H.insert(17, 21);
H.decrease(58, 3);
H.insert(86, 55);
H.pop();
H.insert(4, 92);
H.decrease(68, 49);
H.insert(61, 21);
H.decrease(33, 77);
H.insert(98, 58);
H.decrease(29, 35);
H.insert(29, 34);
H.decrease(83, 32);
H.insert(85, 100);
H.pop();
H.insert(59, 40);
H.insert(92, 39);
H.pop();
H.insert(50, 78);
H.decrease(34, 78);
H.insert(10, 52);
H.pop();
H.insert(87, 13);
H.pop();
H.insert(92, 97);
H.pop();
H.insert(62, 38);
H.decrease(80, 3);
H.insert(72, 48);
H.pop();
H.insert(41, 46);
H.decrease(79, 26);
H.insert(27, 76);
H.insert(55, 35);
H.insert(100, 55);
H.pop();
H.insert(38, 88);
H.pop();
H.insert(68, 79);
H.decrease(86, 92);
H.insert(74, 33);
H.decrease(82, 25);
H.insert(94, 24);
H.decrease(12, 87);
H.insert(79, 64);
H.insert(69, 90);
H.insert(3, 48);
H.insert(41, 53);
H.decrease(85, 33);
H.insert(38, 42);
H.pop();
H.insert(65, 46);
H.insert(37, 90);
H.insert(44, 99);
H.pop();
H.insert(73, 60);
H.pop();
H.insert(33, 99);
H.decrease(78, 45);
H.insert(66, 24);
H.pop();
H.insert(59, 89);
H.insert(97, 60);
H.decrease(32, 10);
H.insert(9, 47);
H.pop();
H.insert(48, 56);
H.insert(28, 16);
H.decrease(56, 77);
H.insert(49, 54);
H.insert(57, 44);
H.insert(30, 16);
H.insert(50, 88);
H.decrease(15, 30);
H.insert(38, 23);
H.insert(66, 66);
H.insert(67, 62);
H.pop();
H.insert(1, 20);
H.decrease(96, 60);
H.insert(99, 11);
H.decrease(94, 62);
H.insert(91, 50);
H.pop();
H.insert(52, 44);
H.insert(9, 52);
H.pop();
H.insert(32, 95);
H.pop();
H.insert(13, 97);
H.decrease(4, 18);
H.insert(22, 60);
H.insert(12, 48);
H.insert(14, 20);
H.decrease(28, 84);
H.insert(89, 66);
H.pop();
H.insert(37, 55);
H.pop();
H.insert(82, 55);
H.pop();
H.insert(96, 79);
H.decrease(72, 53);
H.insert(6, 96);
H.decrease(94, 70);
H.insert(85, 14);
H.insert(39, 11);
H.pop();
H.insert(44, 49);
H.pop();
H.insert(67, 53);
H.insert(11, 48);
H.pop();
H.insert(50, 21);
H.decrease(43, 92);
H.insert(96, 24);
H.decrease(19, 58);
H.insert(92, 43);
H.decrease(84, 2);
std::cerr << H.top().first << std::endl;
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.