lemon/fib_heap.h
author deba
Tue, 03 Jan 2006 16:05:27 +0000
changeset 1870 b9c9b52f839e
parent 1753 98d83dd56c1d
child 1875 98698b69a902
permissions -rw-r--r--
Delete misnamed file
     1 /* -*- C++ -*-
     2  * lemon/fib_heap.h - Part of LEMON, a generic C++ optimization library
     3  *
     4  * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     5  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     6  *
     7  * Permission to use, modify and distribute this software is granted
     8  * provided that this copyright notice appears in all copies. For
     9  * precise terms see the accompanying LICENSE file.
    10  *
    11  * This software is provided "AS IS" with no warranty of any kind,
    12  * express or implied, and with no claim as to its suitability for any
    13  * purpose.
    14  *
    15  */
    16 
    17 #ifndef LEMON_FIB_HEAP_H
    18 #define LEMON_FIB_HEAP_H
    19 
    20 ///\file
    21 ///\ingroup auxdat
    22 ///\brief Fibonacci Heap implementation.
    23 
    24 #include <vector>
    25 #include <functional>
    26 #include <cmath>
    27 
    28 namespace lemon {
    29   
    30   /// \ingroup auxdat
    31 
    32   /// Fibonacci Heap.
    33 
    34   ///This class implements the \e Fibonacci \e heap data structure. A \e heap
    35   ///is a data structure for storing items with specified values called \e
    36   ///priorities in such a way that finding the item with minimum priority is
    37   ///efficient. \c Compare specifies the ordering of the priorities. In a heap
    38   ///one can change the priority of an item, add or erase an item, etc.
    39   ///
    40   ///The methods \ref increase and \ref erase are not efficient in a Fibonacci
    41   ///heap. In case of many calls to these operations, it is better to use a
    42   ///\e binary \e heap.
    43   ///
    44   ///\param Item Type of the items to be stored.  
    45   ///\param Prio Type of the priority of the items.
    46   ///\param ItemIntMap A read and writable Item int map, used internally
    47   ///to handle the cross references.
    48   ///\param Compare A class for the ordering of the priorities. The
    49   ///default is \c std::less<Prio>.
    50   ///
    51   ///\sa BinHeap
    52   ///\sa Dijkstra
    53   ///\author Jacint Szabo 
    54  
    55 #ifdef DOXYGEN
    56   template <typename Item, 
    57 	    typename Prio, 
    58 	    typename ItemIntMap, 
    59 	    typename Compare>
    60 #else
    61   template <typename Item, 
    62 	    typename Prio, 
    63 	    typename ItemIntMap, 
    64 	    typename Compare = std::less<Prio> >
    65 #endif
    66   class FibHeap {
    67   public:     
    68     typedef Prio PrioType;
    69     
    70   private:
    71     class store;
    72     
    73     std::vector<store> container;
    74     int minimum;
    75     ItemIntMap &iimap;
    76     Compare comp;
    77     int num_items;
    78     
    79   public:
    80     ///Status of the nodes
    81     enum state_enum {
    82       ///The node is in the heap
    83       IN_HEAP = 0,
    84       ///The node has never been in the heap
    85       PRE_HEAP = -1,
    86       ///The node was in the heap but it got out of it
    87       POST_HEAP = -2
    88     };
    89     
    90     /// \brief The constructor
    91     ///
    92     /// \c _iimap should be given to the constructor, since it is
    93     ///   used internally to handle the cross references.
    94     explicit FibHeap(ItemIntMap &_iimap) 
    95       : minimum(0), iimap(_iimap), num_items() {} 
    96  
    97     /// \brief The constructor
    98     ///
    99     /// \c _iimap should be given to the constructor, since it is used
   100     /// internally to handle the cross references. \c _comp is an
   101     /// object for ordering of the priorities. 
   102     FibHeap(ItemIntMap &_iimap, const Compare &_comp) : minimum(0), 
   103 		  iimap(_iimap), comp(_comp), num_items() {}
   104     
   105     /// \brief The number of items stored in the heap.
   106     ///
   107     /// Returns the number of items stored in the heap.
   108     int size() const { return num_items; }
   109 
   110     /// \brief Checks if the heap stores no items.
   111     ///
   112     ///   Returns \c true if and only if the heap stores no items.
   113     bool empty() const { return num_items==0; }
   114 
   115     /// \brief Make empty this heap.
   116     /// 
   117     /// Make empty this heap.
   118     void clear() {
   119       if (num_items != 0) {
   120 	for (int i = 0; i < (int)container.size(); ++i) {
   121 	  iimap[container[i].name] = -2;
   122 	}
   123       }
   124       container.clear(); minimum = 0; num_items = 0;
   125     }
   126 
   127     /// \brief \c item gets to the heap with priority \c value independently 
   128     /// if \c item was already there.
   129     ///
   130     /// This method calls \ref push(\c item, \c value) if \c item is not
   131     /// stored in the heap and it calls \ref decrease(\c item, \c value) or
   132     /// \ref increase(\c item, \c value) otherwise.
   133     void set (Item const item, PrioType const value); 
   134     
   135     /// \brief Adds \c item to the heap with priority \c value. 
   136     ///    
   137     /// Adds \c item to the heap with priority \c value. 
   138     /// \pre \c item must not be stored in the heap. 
   139     void push (Item const item, PrioType const value);
   140     
   141     /// \brief Returns the item with minimum priority relative to \c Compare.
   142     ///
   143     /// This method returns the item with minimum priority relative to \c
   144     /// Compare.  
   145     /// \pre The heap must be nonempty.  
   146     Item top() const { return container[minimum].name; }
   147 
   148     /// \brief Returns the minimum priority relative to \c Compare.
   149     ///
   150     /// It returns the minimum priority relative to \c Compare.
   151     /// \pre The heap must be nonempty.
   152     PrioType prio() const { return container[minimum].prio; }
   153     
   154     /// \brief Returns the priority of \c item.
   155     ///
   156     /// This function returns the priority of \c item.
   157     /// \pre \c item must be in the heap.
   158     PrioType& operator[](const Item& item) { 
   159       return container[iimap[item]].prio; 
   160     }
   161     
   162     /// \brief Returns the priority of \c item.
   163     ///
   164     /// It returns the priority of \c item.
   165     /// \pre \c item must be in the heap.
   166     const PrioType& operator[](const Item& item) const { 
   167       return container[iimap[item]].prio; 
   168     }
   169 
   170 
   171     /// \brief Deletes the item with minimum priority relative to \c Compare.
   172     ///
   173     /// This method deletes the item with minimum priority relative to \c
   174     /// Compare from the heap.  
   175     /// \pre The heap must be non-empty.  
   176     void pop();
   177 
   178     /// \brief Deletes \c item from the heap.
   179     ///
   180     /// This method deletes \c item from the heap, if \c item was already
   181     /// stored in the heap. It is quite inefficient in Fibonacci heaps.
   182     void erase (const Item& item); 
   183 
   184     /// \brief Decreases the priority of \c item to \c value.
   185     ///
   186     /// This method decreases the priority of \c item to \c value.
   187     /// \pre \c item must be stored in the heap with priority at least \c
   188     ///   value relative to \c Compare.
   189     void decrease (Item item, PrioType const value); 
   190 
   191     /// \brief Increases the priority of \c item to \c value.
   192     ///
   193     /// This method sets the priority of \c item to \c value. Though
   194     /// there is no precondition on the priority of \c item, this
   195     /// method should be used only if it is indeed necessary to increase
   196     /// (relative to \c Compare) the priority of \c item, because this
   197     /// method is inefficient.
   198     void increase (Item item, PrioType const value) {
   199       erase(item);
   200       push(item, value);
   201     }
   202 
   203 
   204     /// \brief Returns if \c item is in, has already been in, or has never 
   205     /// been in the heap.
   206     ///
   207     /// This method returns PRE_HEAP if \c item has never been in the
   208     /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
   209     /// otherwise. In the latter case it is possible that \c item will
   210     /// get back to the heap again.
   211     state_enum state(const Item &item) const {
   212       int i=iimap[item];
   213       if( i>=0 ) {
   214 	if ( container[i].in ) i=0;
   215 	else i=-2; 
   216       }
   217       return state_enum(i);
   218     }    
   219     
   220   private:
   221     
   222     void balance();
   223     void makeroot(int c);
   224     void cut(int a, int b);
   225     void cascade(int a);
   226     void fuse(int a, int b);
   227     void unlace(int a);
   228 
   229 
   230     class store {
   231       friend class FibHeap;
   232       
   233       Item name;
   234       int parent;
   235       int left_neighbor;
   236       int right_neighbor;
   237       int child;
   238       int degree;  
   239       bool marked;
   240       bool in;
   241       PrioType prio;
   242       
   243       store() : parent(-1), child(-1), degree(), marked(false), in(true) {} 
   244     };
   245   };    
   246  
   247 
   248 
   249     // **********************************************************************
   250     //  IMPLEMENTATIONS
   251     // **********************************************************************
   252     
   253   template <typename Item, typename Prio, typename ItemIntMap, 
   254     typename Compare>
   255   void FibHeap<Item, Prio, ItemIntMap, Compare>::set 
   256   (Item const item, PrioType const value) 
   257   {
   258     int i=iimap[item];
   259     if ( i >= 0 && container[i].in ) {
   260       if ( comp(value, container[i].prio) ) decrease(item, value); 
   261       if ( comp(container[i].prio, value) ) increase(item, value); 
   262     } else push(item, value);
   263   }
   264     
   265   template <typename Item, typename Prio, typename ItemIntMap, 
   266     typename Compare>
   267   void FibHeap<Item, Prio, ItemIntMap, Compare>::push 
   268   (Item const item, PrioType const value) {
   269       int i=iimap[item];      
   270       if ( i < 0 ) {
   271 	int s=container.size();
   272 	iimap.set( item, s );	
   273 	store st;
   274 	st.name=item;
   275 	container.push_back(st);
   276 	i=s;
   277       } else {
   278 	container[i].parent=container[i].child=-1;
   279 	container[i].degree=0;
   280 	container[i].in=true;
   281 	container[i].marked=false;
   282       }
   283 
   284       if ( num_items ) {
   285 	container[container[minimum].right_neighbor].left_neighbor=i;
   286 	container[i].right_neighbor=container[minimum].right_neighbor;
   287 	container[minimum].right_neighbor=i;
   288 	container[i].left_neighbor=minimum;
   289 	if ( comp( value, container[minimum].prio) ) minimum=i; 
   290       } else {
   291 	container[i].right_neighbor=container[i].left_neighbor=i;
   292 	minimum=i;	
   293       }
   294       container[i].prio=value;
   295       ++num_items;
   296     }
   297     
   298   template <typename Item, typename Prio, typename ItemIntMap, 
   299     typename Compare>
   300   void FibHeap<Item, Prio, ItemIntMap, Compare>::pop() {
   301       /*The first case is that there are only one root.*/
   302       if ( container[minimum].left_neighbor==minimum ) {
   303 	container[minimum].in=false;
   304 	if ( container[minimum].degree!=0 ) { 
   305 	  makeroot(container[minimum].child);
   306 	  minimum=container[minimum].child;
   307 	  balance();
   308 	}
   309       } else {
   310 	int right=container[minimum].right_neighbor;
   311 	unlace(minimum);
   312 	container[minimum].in=false;
   313 	if ( container[minimum].degree > 0 ) {
   314 	  int left=container[minimum].left_neighbor;
   315 	  int child=container[minimum].child;
   316 	  int last_child=container[child].left_neighbor;
   317 	
   318 	  makeroot(child);
   319 	  
   320 	  container[left].right_neighbor=child;
   321 	  container[child].left_neighbor=left;
   322 	  container[right].left_neighbor=last_child;
   323 	  container[last_child].right_neighbor=right;
   324 	}
   325 	minimum=right;
   326 	balance();
   327       } // the case where there are more roots
   328       --num_items;   
   329     }
   330 
   331 
   332   template <typename Item, typename Prio, typename ItemIntMap, 
   333     typename Compare>
   334   void FibHeap<Item, Prio, ItemIntMap, Compare>::erase 
   335   (const Item& item) {
   336       int i=iimap[item];
   337       
   338       if ( i >= 0 && container[i].in ) { 	
   339 	if ( container[i].parent!=-1 ) {
   340 	  int p=container[i].parent;
   341 	  cut(i,p);	    
   342 	  cascade(p);
   343 	}
   344 	minimum=i;     //As if its prio would be -infinity
   345 	pop();
   346       }
   347   }
   348     
   349   template <typename Item, typename Prio, typename ItemIntMap, 
   350     typename Compare>
   351   void FibHeap<Item, Prio, ItemIntMap, Compare>::decrease 
   352   (Item item, PrioType const value) {
   353       int i=iimap[item];
   354       container[i].prio=value;
   355       int p=container[i].parent;
   356       
   357       if ( p!=-1 && comp(value, container[p].prio) ) {
   358 	cut(i,p);	    
   359 	cascade(p);
   360       }      
   361       if ( comp(value, container[minimum].prio) ) minimum=i; 
   362   }
   363  
   364 
   365   template <typename Item, typename Prio, typename ItemIntMap, 
   366     typename Compare>
   367   void FibHeap<Item, Prio, ItemIntMap, Compare>::balance() {      
   368 
   369     int maxdeg=int( std::floor( 2.08*log(double(container.size()))))+1;
   370   
   371     std::vector<int> A(maxdeg,-1); 
   372     
   373     /*
   374      *Recall that now minimum does not point to the minimum prio element.
   375      *We set minimum to this during balance().
   376      */
   377     int anchor=container[minimum].left_neighbor; 
   378     int next=minimum; 
   379     bool end=false; 
   380     	
   381        do {
   382 	int active=next;
   383 	if ( anchor==active ) end=true;
   384 	int d=container[active].degree;
   385 	next=container[active].right_neighbor;
   386 
   387 	while (A[d]!=-1) {	  
   388 	  if( comp(container[active].prio, container[A[d]].prio) ) {
   389 	    fuse(active,A[d]); 
   390 	  } else { 
   391 	    fuse(A[d],active);
   392 	    active=A[d];
   393 	  } 
   394 	  A[d]=-1;
   395 	  ++d;
   396 	}	
   397 	A[d]=active;
   398        } while ( !end );
   399 
   400 
   401        while ( container[minimum].parent >=0 ) minimum=container[minimum].parent;
   402        int s=minimum;
   403        int m=minimum;
   404        do {  
   405 	 if ( comp(container[s].prio, container[minimum].prio) ) minimum=s;
   406 	 s=container[s].right_neighbor;
   407        } while ( s != m );
   408     }
   409 
   410   template <typename Item, typename Prio, typename ItemIntMap, 
   411     typename Compare>
   412   void FibHeap<Item, Prio, ItemIntMap, Compare>::makeroot 
   413   (int c) {
   414       int s=c;
   415       do {  
   416 	container[s].parent=-1;
   417 	s=container[s].right_neighbor;
   418       } while ( s != c );
   419     }
   420   
   421   
   422   template <typename Item, typename Prio, typename ItemIntMap, 
   423     typename Compare>
   424   void FibHeap<Item, Prio, ItemIntMap, Compare>::cut 
   425   (int a, int b) {    
   426     /*
   427      *Replacing a from the children of b.
   428      */
   429     --container[b].degree;
   430     
   431     if ( container[b].degree !=0 ) {
   432       int child=container[b].child;
   433       if ( child==a ) 
   434 	container[b].child=container[child].right_neighbor;
   435       unlace(a);
   436     }
   437     
   438     
   439     /*Lacing a to the roots.*/
   440     int right=container[minimum].right_neighbor;
   441     container[minimum].right_neighbor=a;
   442     container[a].left_neighbor=minimum;
   443     container[a].right_neighbor=right;
   444     container[right].left_neighbor=a;
   445     
   446     container[a].parent=-1;
   447     container[a].marked=false;
   448   }
   449   
   450 
   451   template <typename Item, typename Prio, typename ItemIntMap, 
   452     typename Compare>
   453   void FibHeap<Item, Prio, ItemIntMap, Compare>::cascade 
   454   (int a) 
   455     {
   456       if ( container[a].parent!=-1 ) {
   457 	int p=container[a].parent;
   458 	
   459 	if ( container[a].marked==false ) container[a].marked=true;
   460 	else {
   461 	  cut(a,p);
   462 	  cascade(p);
   463 	}
   464       }
   465     }
   466 
   467 
   468   template <typename Item, typename Prio, typename ItemIntMap, 
   469     typename Compare>
   470   void FibHeap<Item, Prio, ItemIntMap, Compare>::fuse 
   471   (int a, int b) {
   472       unlace(b);
   473       
   474       /*Lacing b under a.*/
   475       container[b].parent=a;
   476 
   477       if (container[a].degree==0) {
   478 	container[b].left_neighbor=b;
   479 	container[b].right_neighbor=b;
   480 	container[a].child=b;	
   481       } else {
   482 	int child=container[a].child;
   483 	int last_child=container[child].left_neighbor;
   484 	container[child].left_neighbor=b;
   485 	container[b].right_neighbor=child;
   486 	container[last_child].right_neighbor=b;
   487 	container[b].left_neighbor=last_child;
   488       }
   489 
   490       ++container[a].degree;
   491       
   492       container[b].marked=false;
   493     }
   494 
   495   
   496   /*
   497    *It is invoked only if a has siblings.
   498    */
   499   template <typename Item, typename Prio, typename ItemIntMap, 
   500     typename Compare>
   501   void FibHeap<Item, Prio, ItemIntMap, Compare>::unlace 
   502   (int a) {      
   503       int leftn=container[a].left_neighbor;
   504       int rightn=container[a].right_neighbor;
   505       container[leftn].right_neighbor=rightn;
   506       container[rightn].left_neighbor=leftn;
   507   }
   508   
   509 
   510 } //namespace lemon
   511 
   512 #endif //LEMON_FIB_HEAP_H
   513