Tapkee
fibonacci_heap.hpp
Go to the documentation of this file.
00001 /* This software is distributed under BSD 3-clause license (see LICENSE file).
00002  *
00003  * Copyright (c) 2011-2013 Evgeniy Andreev
00004  */
00005 
00006 #ifndef TAPKEE_FIBONACCI_H_
00007 #define TAPKEE_FIBONACCI_H_
00008 
00009 /* Tapkee includes */
00010 #include <tapkee/defines.hpp>
00011 /* End of Tapkee includes */
00012 
00013 #include <cmath>
00014 
00015 namespace tapkee
00016 {
00017 namespace tapkee_internal
00018 {
00019 
00020 struct fibonacci_heap_node
00021 {
00022     fibonacci_heap_node() : parent(NULL), child(NULL), left(NULL), right(NULL),
00023         rank(0), marked(false), index(-1), key(0.0)
00024     {
00025     }
00026 
00028     fibonacci_heap_node* parent;
00029 
00031     fibonacci_heap_node* child;
00032 
00034     fibonacci_heap_node* left;
00035 
00037     fibonacci_heap_node* right;
00038 
00040     int rank;
00041 
00043     bool marked;
00044 
00046     int index;
00047 
00049     ScalarType key;
00050 
00051 private:
00052     fibonacci_heap_node(const fibonacci_heap_node& fh);
00053     fibonacci_heap_node& operator=(const fibonacci_heap_node& fh);
00054 };
00055 
00062 class fibonacci_heap
00063 {
00064 public:
00065 
00067     fibonacci_heap(int capacity) : 
00068         min_root(NULL), nodes(NULL), num_nodes(0),
00069         num_trees(0), max_num_nodes(capacity), A(NULL), Dn(0)
00070     {
00071         nodes = (fibonacci_heap_node**)malloc(sizeof(fibonacci_heap_node*)*max_num_nodes);
00072         for (int i = 0; i < max_num_nodes; i++)
00073             nodes[i] = new fibonacci_heap_node;
00074 
00075         Dn = 1 + (int)(log(ScalarType(max_num_nodes))/log(2.));
00076         A = (fibonacci_heap_node**)malloc(sizeof(fibonacci_heap_node*)*Dn);
00077         for (int i = 0; i < Dn; i++)
00078             A[i] = NULL;
00079 
00080         num_nodes = 0;
00081         num_trees = 0;
00082     }
00083 
00084     ~fibonacci_heap()
00085     {
00086         for(int i = 0; i < max_num_nodes; i++)
00087         {
00088             if(nodes[i] != NULL)
00089                 delete nodes[i];
00090         }
00091         free(nodes);
00092         free(A);
00093     }
00094 
00098     void insert(int index, ScalarType key)
00099     {
00100         if(index >= static_cast<int>(max_num_nodes) || index < 0)
00101             return;
00102 
00103         if(nodes[index]->index != -1)
00104             return; // node is not empty
00105 
00106         // init "new" node in array
00107         nodes[index]->child = NULL;
00108         nodes[index]->parent = NULL;
00109 
00110         nodes[index]->rank = 0;
00111         nodes[index]->index = index;
00112         nodes[index]->key = key;
00113         nodes[index]->marked = false;
00114 
00115         add_to_roots(nodes[index]);
00116         num_nodes++;
00117     }
00118 
00119     bool empty() const 
00120     {
00121         return num_nodes==0;
00122     }
00123 
00124     int get_num_nodes() const
00125     {
00126         return num_nodes;
00127     }
00128 
00129     int get_num_trees()
00130     {
00131         return num_trees;
00132     }
00133 
00134     int get_capacity()
00135     {
00136         return max_num_nodes;
00137     }
00138 
00143     int extract_min(ScalarType& ret_key)
00144     {
00145         fibonacci_heap_node *min_node;
00146         fibonacci_heap_node *child, *next_child;
00147 
00148         int result;
00149 
00150         if(num_nodes == 0)
00151             return -1;
00152 
00153         min_node = min_root;
00154         if(min_node == NULL)
00155             return -1; // heap is empty now
00156 
00157         child = min_node->child;
00158         while(child != NULL && child->parent != NULL)
00159         {
00160             next_child = child->right;
00161 
00162             // delete current child from childs list
00163             child->left->right = child->right;
00164             child->right->left = child->left;
00165 
00166             add_to_roots(child);
00167 
00168             // next iteration
00169             child = next_child;
00170         }
00171 
00172         // delete minimun from root list
00173         min_node->left->right = min_node->right;
00174         min_node->right->left = min_node->left;
00175 
00176         num_trees--;
00177 
00178         if(min_node == min_node->right)
00179         {
00180             min_root = NULL; // remove last element
00181         }
00182         else
00183         {
00184             min_root = min_node->right;
00185             consolidate();
00186         }
00187 
00188         result = min_node->index;
00189         ret_key = min_node->key;
00190         clear_node(result);
00191 
00192         num_nodes--;
00193 
00194         return result;
00195     }
00196 
00198     void clear()
00199     {
00200         min_root = NULL;
00201 
00202         // clear all nodes
00203         for(int i = 0; i < max_num_nodes; i++)
00204         {
00205             clear_node(i);
00206         }
00207 
00208         num_nodes = 0;
00209         num_trees = 0;
00210     }
00211 
00215     int get_key(int index, ScalarType& ret_key)
00216     {
00217         if(index >= max_num_nodes || index < 0)
00218             return -1;
00219         if(nodes[index]->index == -1)
00220             return -1;
00221 
00222         int result = nodes[index]->index;
00223         ret_key = nodes[index]->key;
00224 
00225         return result;
00226     }
00227 
00231     void decrease_key(int index, ScalarType& key)
00232     {
00233         fibonacci_heap_node* parent;
00234 
00235         if(index >= max_num_nodes || index < 0)
00236             return;
00237         if(nodes[index]->index == -1)
00238             return; // node is empty
00239         if(key > nodes[index]->key)
00240             return;
00241 
00242 
00243         nodes[index]->key = key;
00244 
00245         parent = nodes[index]->parent;
00246 
00247         if(parent != NULL && nodes[index]->key < parent->key)
00248         {
00249             cut(nodes[index], parent);
00250             cascading_cut(parent);
00251         }
00252 
00253         if(nodes[index]->key < min_root->key)
00254             min_root = nodes[index];
00255     }
00256 
00257 private:
00258 
00259     fibonacci_heap();
00260     fibonacci_heap(const fibonacci_heap& fh);
00261     fibonacci_heap& operator=(const fibonacci_heap& fh);
00262 
00263 private:
00265     void add_to_roots(fibonacci_heap_node *up_node)
00266     {
00267         if(min_root == NULL)
00268         {
00269             // if heap is empty, node becomes circular root list
00270             min_root = up_node;
00271 
00272             up_node->left = up_node;
00273             up_node->right = up_node;
00274         }
00275         else
00276         {
00277             // insert node to root list
00278             up_node->right = min_root->right;
00279             up_node->left = min_root;
00280 
00281             up_node->left->right = up_node;
00282             up_node->right->left = up_node;
00283 
00284             // nomination of new minimum node
00285             if(up_node->key < min_root->key)
00286             {
00287                 min_root = up_node;
00288             }
00289         }
00290 
00291         up_node->parent = NULL;
00292         num_trees++;
00293     }
00294 
00296     void consolidate()
00297     {
00298         fibonacci_heap_node *x, *y, *w;
00299         int d;
00300 
00301         for(int i = 0; i < Dn; i++)
00302         {
00303             A[i] = NULL;
00304         }
00305 
00306         min_root->left->right = NULL;
00307         min_root->left = NULL;
00308         w = min_root;
00309 
00310         do
00311         {
00312             x = w;
00313             d = x->rank;
00314             w = w->right;
00315 
00316             while(A[d] != NULL)
00317             {
00318                 y = A[d];
00319 
00320                 if(y->key < x->key)
00321                 {
00322                     fibonacci_heap_node *temp;
00323 
00324                     temp = y;
00325                     y = x;
00326                     x = temp;
00327                 }
00328 
00329                 link_nodes(y, x);
00330 
00331                 A[d] = NULL;
00332                 d++;
00333             }
00334             A[d] = x;
00335         }
00336         while(w != NULL);
00337 
00338         min_root = NULL;
00339         num_trees = 0;
00340 
00341         for(int i = 0; i < Dn; i++)
00342         {
00343             if(A[i] != NULL)
00344             {
00345                 A[i]->marked = false;
00346                 add_to_roots(A[i]);
00347             }
00348         }
00349     }
00350 
00352     void link_nodes(fibonacci_heap_node *y, fibonacci_heap_node *x)
00353     {
00354         if(y->right != NULL)
00355             y->right->left = y->left;
00356         if(y->left != NULL)
00357             y->left->right = y->right;
00358 
00359         num_trees--;
00360 
00361         y->left = y;
00362         y->right = y;
00363 
00364         y->parent = x;
00365 
00366         if(x->child == NULL)
00367         {
00368             x->child = y;
00369         }
00370         else
00371         {
00372             y->left = x->child;
00373             y->right = x->child->right;
00374 
00375             x->child->right = y;
00376             y->right->left = y;
00377         }
00378 
00379         x->rank++;
00380 
00381         y->marked = false;
00382     }
00383 
00385     void clear_node(int index)
00386     {
00387         nodes[index]->parent = NULL;
00388         nodes[index]->child = NULL;
00389         nodes[index]->left = NULL;
00390         nodes[index]->right = NULL;
00391 
00392         nodes[index]->rank = 0;
00393         nodes[index]->index = -1;
00394         nodes[index]->key = 0;
00395 
00396         nodes[index]->marked = false;
00397     }
00398 
00400     void cut(fibonacci_heap_node *child, fibonacci_heap_node *parent)
00401     {
00402         if(parent->child == child)
00403             parent->child = child->right;
00404 
00405         if(parent->child == child)
00406             parent->child = NULL;
00407 
00408         parent->rank--;
00409 
00410         child->left->right = child->right;
00411         child->right->left = child->left;
00412         child->marked = false;
00413 
00414         add_to_roots(child);
00415     }
00416 
00417     void cascading_cut(fibonacci_heap_node* tree)
00418     {
00419         fibonacci_heap_node *temp;
00420 
00421         temp = tree->parent;
00422         if(temp != NULL)
00423         {
00424             if(!tree->marked)
00425             {
00426                 tree->marked = true;
00427             }
00428             else
00429             {
00430                 cut(tree, temp);
00431                 cascading_cut(temp);
00432             }
00433         }
00434     }
00435 
00436 protected:
00438     fibonacci_heap_node* min_root;
00439 
00441     fibonacci_heap_node** nodes;
00442 
00444     int num_nodes;
00445 
00447     int num_trees;
00448 
00450     int max_num_nodes;
00451 
00453     fibonacci_heap_node **A;
00454 
00456     int Dn;
00457 };
00458 
00459 }
00460 }
00461 
00462 #endif /* FIBONACCI_H_ */
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines