6 #ifndef TAPKEE_FIBONACCI_H_ 7 #define TAPKEE_FIBONACCI_H_ 17 namespace tapkee_internal
68 min_root(NULL), nodes(NULL), num_nodes(0),
69 num_trees(0), max_num_nodes(capacity), A(NULL), Dn(0)
72 for (
int i = 0; i < max_num_nodes; i++)
75 Dn = 1 + (int)(log(
ScalarType(max_num_nodes))/log(2.));
77 for (
int i = 0; i < Dn; i++)
86 for(
int i = 0; i < max_num_nodes; i++)
100 if(index >= static_cast<int>(max_num_nodes) || index < 0)
103 if(nodes[index]->index != -1)
107 nodes[
index]->child = NULL;
108 nodes[
index]->parent = NULL;
110 nodes[
index]->rank = 0;
113 nodes[
index]->marked =
false;
115 add_to_roots(nodes[index]);
136 return max_num_nodes;
157 child = min_node->
child;
158 while(child != NULL && child->
parent != NULL)
160 next_child = child->
right;
178 if(min_node == min_node->
right)
184 min_root = min_node->
right;
188 result = min_node->
index;
189 ret_key = min_node->
key;
203 for(
int i = 0; i < max_num_nodes; i++)
217 if(index >= max_num_nodes || index < 0)
219 if(nodes[index]->index == -1)
222 int result = nodes[
index]->index;
223 ret_key = nodes[
index]->key;
235 if(index >= max_num_nodes || index < 0)
237 if(nodes[index]->index == -1)
239 if(key > nodes[index]->key)
247 if(parent != NULL && nodes[index]->key < parent->key)
249 cut(nodes[index], parent);
250 cascading_cut(parent);
253 if(nodes[index]->key < min_root->key)
254 min_root = nodes[
index];
272 up_node->
left = up_node;
273 up_node->
right = up_node;
279 up_node->
left = min_root;
285 if(up_node->
key < min_root->key)
301 for(
int i = 0; i < Dn; i++)
307 min_root->
left = NULL;
341 for(
int i = 0; i < Dn; i++)
387 nodes[
index]->parent = NULL;
388 nodes[
index]->child = NULL;
389 nodes[
index]->left = NULL;
390 nodes[
index]->right = NULL;
392 nodes[
index]->rank = 0;
393 nodes[
index]->index = -1;
394 nodes[
index]->key = 0;
396 nodes[
index]->marked =
false;
402 if(parent->
child == child)
405 if(parent->
child == child)
406 parent->
child = NULL;
void cut(fibonacci_heap_node *child, fibonacci_heap_node *parent)
fibonacci_heap_node ** nodes
int extract_min(ScalarType &ret_key)
fibonacci_heap_node * left
fibonacci_heap(int capacity)
void add_to_roots(fibonacci_heap_node *up_node)
double ScalarType
default scalar value (can be overrided with TAPKEE_CUSTOM_INTERNAL_NUMTYPE define) ...
int get_key(int index, ScalarType &ret_key)
int get_num_nodes() const
fibonacci_heap_node * parent
void decrease_key(int index, ScalarType &key)
fibonacci_heap_node & operator=(const fibonacci_heap_node &fh)
void insert(int index, ScalarType key)
fibonacci_heap_node * child
void cascading_cut(fibonacci_heap_node *tree)
void clear_node(int index)
void link_nodes(fibonacci_heap_node *y, fibonacci_heap_node *x)
fibonacci_heap_node * min_root
the class fibonacci_heap, a fibonacci heap. Generally used by Isomap for Dijkstra heap algorithm ...
fibonacci_heap_node * right