Tapkee
fibonacci_heap.hpp
Go to the documentation of this file.
1 /* This software is distributed under BSD 3-clause license (see LICENSE file).
2  *
3  * Copyright (c) 2011-2013 Evgeniy Andreev
4  */
5 
6 #ifndef TAPKEE_FIBONACCI_H_
7 #define TAPKEE_FIBONACCI_H_
8 
9 /* Tapkee includes */
10 #include <tapkee/defines.hpp>
11 /* End of Tapkee includes */
12 
13 #include <cmath>
14 
15 namespace tapkee
16 {
17 namespace tapkee_internal
18 {
19 
21 {
22  fibonacci_heap_node() : parent(NULL), child(NULL), left(NULL), right(NULL),
23  rank(0), marked(false), index(-1), key(0.0)
24  {
25  }
26 
29 
32 
35 
38 
40  int rank;
41 
43  bool marked;
44 
46  int index;
47 
50 
51 private:
54 };
55 
63 {
64 public:
65 
67  fibonacci_heap(int capacity) :
68  min_root(NULL), nodes(NULL), num_nodes(0),
69  num_trees(0), max_num_nodes(capacity), A(NULL), Dn(0)
70  {
71  nodes = (fibonacci_heap_node**)malloc(sizeof(fibonacci_heap_node*)*max_num_nodes);
72  for (int i = 0; i < max_num_nodes; i++)
73  nodes[i] = new fibonacci_heap_node;
74 
75  Dn = 1 + (int)(log(ScalarType(max_num_nodes))/log(2.));
76  A = (fibonacci_heap_node**)malloc(sizeof(fibonacci_heap_node*)*Dn);
77  for (int i = 0; i < Dn; i++)
78  A[i] = NULL;
79 
80  num_nodes = 0;
81  num_trees = 0;
82  }
83 
85  {
86  for(int i = 0; i < max_num_nodes; i++)
87  {
88  delete nodes[i];
89  }
90  free(nodes);
91  free(A);
92  }
93 
98  {
99  if(index >= static_cast<int>(max_num_nodes) || index < 0)
100  return;
101 
102  if(nodes[index]->index != -1)
103  return; // node is not empty
104 
105  // init "new" node in array
106  nodes[index]->child = NULL;
107  nodes[index]->parent = NULL;
108 
109  nodes[index]->rank = 0;
110  nodes[index]->index = index;
111  nodes[index]->key = key;
112  nodes[index]->marked = false;
113 
114  add_to_roots(nodes[index]);
115  num_nodes++;
116  }
117 
118  bool empty() const
119  {
120  return num_nodes==0;
121  }
122 
123  int get_num_nodes() const
124  {
125  return num_nodes;
126  }
127 
129  {
130  return num_trees;
131  }
132 
134  {
135  return max_num_nodes;
136  }
137 
142  int extract_min(ScalarType& ret_key)
143  {
144  fibonacci_heap_node *min_node;
145  fibonacci_heap_node *child, *next_child;
146 
147  int result;
148 
149  if(num_nodes == 0)
150  return -1;
151 
152  min_node = min_root;
153  if(min_node == NULL)
154  return -1; // heap is empty now
155 
156  child = min_node->child;
157  while(child != NULL && child->parent != NULL)
158  {
159  next_child = child->right;
160 
161  // delete current child from childs list
162  child->left->right = child->right;
163  child->right->left = child->left;
164 
165  add_to_roots(child);
166 
167  // next iteration
168  child = next_child;
169  }
170 
171  // delete minimun from root list
172  min_node->left->right = min_node->right;
173  min_node->right->left = min_node->left;
174 
175  num_trees--;
176 
177  if(min_node == min_node->right)
178  {
179  min_root = NULL; // remove last element
180  }
181  else
182  {
183  min_root = min_node->right;
184  consolidate();
185  }
186 
187  result = min_node->index;
188  ret_key = min_node->key;
189  clear_node(result);
190 
191  num_nodes--;
192 
193  return result;
194  }
195 
197  void clear()
198  {
199  min_root = NULL;
200 
201  // clear all nodes
202  for(int i = 0; i < max_num_nodes; i++)
203  {
204  clear_node(i);
205  }
206 
207  num_nodes = 0;
208  num_trees = 0;
209  }
210 
214  int get_key(int index, ScalarType& ret_key)
215  {
216  if(index >= max_num_nodes || index < 0)
217  return -1;
218  if(nodes[index]->index == -1)
219  return -1;
220 
221  int result = nodes[index]->index;
222  ret_key = nodes[index]->key;
223 
224  return result;
225  }
226 
231  {
233 
234  if(index >= max_num_nodes || index < 0)
235  return;
236  if(nodes[index]->index == -1)
237  return; // node is empty
238  if(key > nodes[index]->key)
239  return;
240 
241 
242  nodes[index]->key = key;
243 
244  parent = nodes[index]->parent;
245 
246  if(parent != NULL && nodes[index]->key < parent->key)
247  {
248  cut(nodes[index], parent);
249  cascading_cut(parent);
250  }
251 
252  if(nodes[index]->key < min_root->key)
253  min_root = nodes[index];
254  }
255 
256 private:
257 
258  fibonacci_heap();
259  fibonacci_heap(const fibonacci_heap& fh);
261 
262 private:
265  {
266  if(min_root == NULL)
267  {
268  // if heap is empty, node becomes circular root list
269  min_root = up_node;
270 
271  up_node->left = up_node;
272  up_node->right = up_node;
273  }
274  else
275  {
276  // insert node to root list
277  up_node->right = min_root->right;
278  up_node->left = min_root;
279 
280  up_node->left->right = up_node;
281  up_node->right->left = up_node;
282 
283  // nomination of new minimum node
284  if(up_node->key < min_root->key)
285  {
286  min_root = up_node;
287  }
288  }
289 
290  up_node->parent = NULL;
291  num_trees++;
292  }
293 
295  void consolidate()
296  {
297  fibonacci_heap_node *x, *y, *w;
298  int d;
299 
300  for(int i = 0; i < Dn; i++)
301  {
302  A[i] = NULL;
303  }
304 
305  min_root->left->right = NULL;
306  min_root->left = NULL;
307  w = min_root;
308 
309  do
310  {
311  x = w;
312  d = x->rank;
313  w = w->right;
314 
315  while(A[d] != NULL)
316  {
317  y = A[d];
318 
319  if(y->key < x->key)
320  {
321  fibonacci_heap_node *temp;
322 
323  temp = y;
324  y = x;
325  x = temp;
326  }
327 
328  link_nodes(y, x);
329 
330  A[d] = NULL;
331  d++;
332  }
333  A[d] = x;
334  }
335  while(w != NULL);
336 
337  min_root = NULL;
338  num_trees = 0;
339 
340  for(int i = 0; i < Dn; i++)
341  {
342  if(A[i] != NULL)
343  {
344  A[i]->marked = false;
345  add_to_roots(A[i]);
346  }
347  }
348  }
349 
352  {
353  if(y->right != NULL)
354  y->right->left = y->left;
355  if(y->left != NULL)
356  y->left->right = y->right;
357 
358  num_trees--;
359 
360  y->left = y;
361  y->right = y;
362 
363  y->parent = x;
364 
365  if(x->child == NULL)
366  {
367  x->child = y;
368  }
369  else
370  {
371  y->left = x->child;
372  y->right = x->child->right;
373 
374  x->child->right = y;
375  y->right->left = y;
376  }
377 
378  x->rank++;
379 
380  y->marked = false;
381  }
382 
384  void clear_node(int index)
385  {
386  nodes[index]->parent = NULL;
387  nodes[index]->child = NULL;
388  nodes[index]->left = NULL;
389  nodes[index]->right = NULL;
390 
391  nodes[index]->rank = 0;
392  nodes[index]->index = -1;
393  nodes[index]->key = 0;
394 
395  nodes[index]->marked = false;
396  }
397 
400  {
401  if(parent->child == child)
402  parent->child = child->right;
403 
404  if(parent->child == child)
405  parent->child = NULL;
406 
407  parent->rank--;
408 
409  child->left->right = child->right;
410  child->right->left = child->left;
411  child->marked = false;
412 
413  add_to_roots(child);
414  }
415 
417  {
418  fibonacci_heap_node *temp;
419 
420  temp = tree->parent;
421  if(temp != NULL)
422  {
423  if(!tree->marked)
424  {
425  tree->marked = true;
426  }
427  else
428  {
429  cut(tree, temp);
430  cascading_cut(temp);
431  }
432  }
433  }
434 
435 protected:
438 
441 
444 
447 
450 
453 
455  int Dn;
456 };
457 
458 }
459 }
460 
461 #endif /* FIBONACCI_H_ */
void cut(fibonacci_heap_node *child, fibonacci_heap_node *parent)
void add_to_roots(fibonacci_heap_node *up_node)
double ScalarType
default scalar value (can be overrided with TAPKEE_CUSTOM_INTERNAL_NUMTYPE define) ...
Definition: types.hpp:15
int get_key(int index, ScalarType &ret_key)
void decrease_key(int index, ScalarType &key)
fibonacci_heap_node & operator=(const fibonacci_heap_node &fh)
void insert(int index, ScalarType key)
void cascading_cut(fibonacci_heap_node *tree)
void link_nodes(fibonacci_heap_node *y, fibonacci_heap_node *x)
the class fibonacci_heap, a fibonacci heap. Generally used by Isomap for Dijkstra heap algorithm ...