Tapkee
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
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  {
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  if(nodes[i] != NULL)
89  delete nodes[i];
90  }
91  free(nodes);
92  free(A);
93  }
94 
98  void insert(int index, ScalarType key)
99  {
100  if(index >= static_cast<int>(max_num_nodes) || index < 0)
101  return;
102 
103  if(nodes[index]->index != -1)
104  return; // node is not empty
105 
106  // init "new" node in array
107  nodes[index]->child = NULL;
108  nodes[index]->parent = NULL;
109 
110  nodes[index]->rank = 0;
111  nodes[index]->index = index;
112  nodes[index]->key = key;
113  nodes[index]->marked = false;
114 
115  add_to_roots(nodes[index]);
116  num_nodes++;
117  }
118 
119  bool empty() const
120  {
121  return num_nodes==0;
122  }
123 
124  int get_num_nodes() const
125  {
126  return num_nodes;
127  }
128 
130  {
131  return num_trees;
132  }
133 
135  {
136  return max_num_nodes;
137  }
138 
143  int extract_min(ScalarType& ret_key)
144  {
145  fibonacci_heap_node *min_node;
146  fibonacci_heap_node *child, *next_child;
147 
148  int result;
149 
150  if(num_nodes == 0)
151  return -1;
152 
153  min_node = min_root;
154  if(min_node == NULL)
155  return -1; // heap is empty now
156 
157  child = min_node->child;
158  while(child != NULL && child->parent != NULL)
159  {
160  next_child = child->right;
161 
162  // delete current child from childs list
163  child->left->right = child->right;
164  child->right->left = child->left;
165 
166  add_to_roots(child);
167 
168  // next iteration
169  child = next_child;
170  }
171 
172  // delete minimun from root list
173  min_node->left->right = min_node->right;
174  min_node->right->left = min_node->left;
175 
176  num_trees--;
177 
178  if(min_node == min_node->right)
179  {
180  min_root = NULL; // remove last element
181  }
182  else
183  {
184  min_root = min_node->right;
185  consolidate();
186  }
187 
188  result = min_node->index;
189  ret_key = min_node->key;
190  clear_node(result);
191 
192  num_nodes--;
193 
194  return result;
195  }
196 
198  void clear()
199  {
200  min_root = NULL;
201 
202  // clear all nodes
203  for(int i = 0; i < max_num_nodes; i++)
204  {
205  clear_node(i);
206  }
207 
208  num_nodes = 0;
209  num_trees = 0;
210  }
211 
215  int get_key(int index, ScalarType& ret_key)
216  {
217  if(index >= max_num_nodes || index < 0)
218  return -1;
219  if(nodes[index]->index == -1)
220  return -1;
221 
222  int result = nodes[index]->index;
223  ret_key = nodes[index]->key;
224 
225  return result;
226  }
227 
231  void decrease_key(int index, ScalarType& key)
232  {
233  fibonacci_heap_node* parent;
234 
235  if(index >= max_num_nodes || index < 0)
236  return;
237  if(nodes[index]->index == -1)
238  return; // node is empty
239  if(key > nodes[index]->key)
240  return;
241 
242 
243  nodes[index]->key = key;
244 
245  parent = nodes[index]->parent;
246 
247  if(parent != NULL && nodes[index]->key < parent->key)
248  {
249  cut(nodes[index], parent);
250  cascading_cut(parent);
251  }
252 
253  if(nodes[index]->key < min_root->key)
254  min_root = nodes[index];
255  }
256 
257 private:
258 
259  fibonacci_heap();
260  fibonacci_heap(const fibonacci_heap& fh);
262 
263 private:
266  {
267  if(min_root == NULL)
268  {
269  // if heap is empty, node becomes circular root list
270  min_root = up_node;
271 
272  up_node->left = up_node;
273  up_node->right = up_node;
274  }
275  else
276  {
277  // insert node to root list
278  up_node->right = min_root->right;
279  up_node->left = min_root;
280 
281  up_node->left->right = up_node;
282  up_node->right->left = up_node;
283 
284  // nomination of new minimum node
285  if(up_node->key < min_root->key)
286  {
287  min_root = up_node;
288  }
289  }
290 
291  up_node->parent = NULL;
292  num_trees++;
293  }
294 
296  void consolidate()
297  {
298  fibonacci_heap_node *x, *y, *w;
299  int d;
300 
301  for(int i = 0; i < Dn; i++)
302  {
303  A[i] = NULL;
304  }
305 
306  min_root->left->right = NULL;
307  min_root->left = NULL;
308  w = min_root;
309 
310  do
311  {
312  x = w;
313  d = x->rank;
314  w = w->right;
315 
316  while(A[d] != NULL)
317  {
318  y = A[d];
319 
320  if(y->key < x->key)
321  {
322  fibonacci_heap_node *temp;
323 
324  temp = y;
325  y = x;
326  x = temp;
327  }
328 
329  link_nodes(y, x);
330 
331  A[d] = NULL;
332  d++;
333  }
334  A[d] = x;
335  }
336  while(w != NULL);
337 
338  min_root = NULL;
339  num_trees = 0;
340 
341  for(int i = 0; i < Dn; i++)
342  {
343  if(A[i] != NULL)
344  {
345  A[i]->marked = false;
346  add_to_roots(A[i]);
347  }
348  }
349  }
350 
353  {
354  if(y->right != NULL)
355  y->right->left = y->left;
356  if(y->left != NULL)
357  y->left->right = y->right;
358 
359  num_trees--;
360 
361  y->left = y;
362  y->right = y;
363 
364  y->parent = x;
365 
366  if(x->child == NULL)
367  {
368  x->child = y;
369  }
370  else
371  {
372  y->left = x->child;
373  y->right = x->child->right;
374 
375  x->child->right = y;
376  y->right->left = y;
377  }
378 
379  x->rank++;
380 
381  y->marked = false;
382  }
383 
385  void clear_node(int index)
386  {
387  nodes[index]->parent = NULL;
388  nodes[index]->child = NULL;
389  nodes[index]->left = NULL;
390  nodes[index]->right = NULL;
391 
392  nodes[index]->rank = 0;
393  nodes[index]->index = -1;
394  nodes[index]->key = 0;
395 
396  nodes[index]->marked = false;
397  }
398 
401  {
402  if(parent->child == child)
403  parent->child = child->right;
404 
405  if(parent->child == child)
406  parent->child = NULL;
407 
408  parent->rank--;
409 
410  child->left->right = child->right;
411  child->right->left = child->left;
412  child->marked = false;
413 
414  add_to_roots(child);
415  }
416 
418  {
419  fibonacci_heap_node *temp;
420 
421  temp = tree->parent;
422  if(temp != NULL)
423  {
424  if(!tree->marked)
425  {
426  tree->marked = true;
427  }
428  else
429  {
430  cut(tree, temp);
431  cascading_cut(temp);
432  }
433  }
434  }
435 
436 protected:
439 
442 
445 
448 
451 
454 
456  int Dn;
457 };
458 
459 }
460 }
461 
462 #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)
fibonacci_heap & operator=(const fibonacci_heap &fh)
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 ...