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++)
99 if(index >= static_cast<int>(max_num_nodes) || index < 0)
102 if(nodes[index]->index != -1)
106 nodes[
index]->child = NULL;
107 nodes[
index]->parent = NULL;
109 nodes[
index]->rank = 0;
112 nodes[
index]->marked =
false;
114 add_to_roots(nodes[index]);
135 return max_num_nodes;
156 child = min_node->
child;
157 while(child != NULL && child->
parent != NULL)
159 next_child = child->
right;
177 if(min_node == min_node->
right)
183 min_root = min_node->
right;
187 result = min_node->
index;
188 ret_key = min_node->
key;
202 for(
int i = 0; i < max_num_nodes; i++)
216 if(index >= max_num_nodes || index < 0)
218 if(nodes[index]->index == -1)
221 int result = nodes[
index]->index;
222 ret_key = nodes[
index]->key;
234 if(index >= max_num_nodes || index < 0)
236 if(nodes[index]->index == -1)
238 if(key > nodes[index]->key)
246 if(parent != NULL && nodes[index]->key < parent->key)
248 cut(nodes[index], parent);
249 cascading_cut(parent);
252 if(nodes[index]->key < min_root->key)
253 min_root = nodes[
index];
271 up_node->
left = up_node;
272 up_node->
right = up_node;
278 up_node->
left = min_root;
284 if(up_node->
key < min_root->key)
300 for(
int i = 0; i < Dn; i++)
306 min_root->
left = NULL;
340 for(
int i = 0; i < Dn; i++)
386 nodes[
index]->parent = NULL;
387 nodes[
index]->child = NULL;
388 nodes[
index]->left = NULL;
389 nodes[
index]->right = NULL;
391 nodes[
index]->rank = 0;
392 nodes[
index]->index = -1;
393 nodes[
index]->key = 0;
395 nodes[
index]->marked =
false;
401 if(parent->
child == child)
404 if(parent->
child == child)
405 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
int get_num_nodes() const
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)
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