lemon/binom_heap.h
changeset 733 abf31e4af617
parent 703 bb3392fe91f2
equal deleted inserted replaced
1:4a920e9e25a5 2:847a7cba7470
    77       PRE_HEAP = -1,  ///< = -1.
    77       PRE_HEAP = -1,  ///< = -1.
    78       POST_HEAP = -2  ///< = -2.
    78       POST_HEAP = -2  ///< = -2.
    79     };
    79     };
    80 
    80 
    81   private:
    81   private:
    82     class store;
    82     class Store;
    83 
    83 
    84     std::vector<store> _data;
    84     std::vector<Store> _data;
    85     int _min, _head;
    85     int _min, _head;
    86     ItemIntMap &_iim;
    86     ItemIntMap &_iim;
    87     Compare _comp;
    87     Compare _comp;
    88     int _num_items;
    88     int _num_items;
    89 
    89 
   154     void push (const Item& item, const Prio& value) {
   154     void push (const Item& item, const Prio& value) {
   155       int i=_iim[item];
   155       int i=_iim[item];
   156       if ( i<0 ) {
   156       if ( i<0 ) {
   157         int s=_data.size();
   157         int s=_data.size();
   158         _iim.set( item,s );
   158         _iim.set( item,s );
   159         store st;
   159         Store st;
   160         st.name=item;
   160         st.name=item;
       
   161         st.prio=value;
   161         _data.push_back(st);
   162         _data.push_back(st);
   162         i=s;
   163         i=s;
   163       }
   164       }
   164       else {
   165       else {
   165         _data[i].parent=_data[i].right_neighbor=_data[i].child=-1;
   166         _data[i].parent=_data[i].right_neighbor=_data[i].child=-1;
   166         _data[i].degree=0;
   167         _data[i].degree=0;
   167         _data[i].in=true;
   168         _data[i].in=true;
   168       }
   169         _data[i].prio=value;
   169       _data[i].prio=value;
   170       }
   170 
   171 
   171       if( 0==_num_items ) { _head=i; _min=i; }
   172       if( 0==_num_items ) {
   172       else { merge(i); }
   173         _head=i;
   173 
   174         _min=i;
   174       _min = findMin();
   175       } else {
   175 
   176         merge(i);
       
   177         if( _comp(_data[i].prio, _data[_min].prio) ) _min=i;
       
   178       }
   176       ++_num_items;
   179       ++_num_items;
   177     }
   180     }
   178 
   181 
   179     /// \brief Return the item having minimum priority.
   182     /// \brief Return the item having minimum priority.
   180     ///
   183     ///
   206 
   209 
   207       int head_child=-1;
   210       int head_child=-1;
   208       if ( _data[_min].child!=-1 ) {
   211       if ( _data[_min].child!=-1 ) {
   209         int child=_data[_min].child;
   212         int child=_data[_min].child;
   210         int neighb;
   213         int neighb;
   211         int prev=-1;
       
   212         while( child!=-1 ) {
   214         while( child!=-1 ) {
   213           neighb=_data[child].right_neighbor;
   215           neighb=_data[child].right_neighbor;
   214           _data[child].parent=-1;
   216           _data[child].parent=-1;
   215           _data[child].right_neighbor=prev;
   217           _data[child].right_neighbor=head_child;
   216           head_child=child;
   218           head_child=child;
   217           prev=child;
       
   218           child=neighb;
   219           child=neighb;
   219         }
   220         }
   220       }
   221       }
   221 
   222 
   222       // The first case is that there are only one root.
   223       if ( _data[_head].right_neighbor==-1 ) {
   223       if ( -1==_data[_head].right_neighbor ) {
   224         // there was only one root
   224         _head=head_child;
   225         _head=head_child;
   225       }
   226       }
   226       // The case where there are more roots.
       
   227       else {
   227       else {
       
   228         // there were more roots
   228         if( _head!=_min )  { unlace(_min); }
   229         if( _head!=_min )  { unlace(_min); }
   229         else { _head=_data[_head].right_neighbor; }
   230         else { _head=_data[_head].right_neighbor; }
   230 
       
   231         merge(head_child);
   231         merge(head_child);
   232       }
   232       }
   233       _min=findMin();
   233       _min=findMin();
   234       --_num_items;
   234       --_num_items;
   235     }
   235     }
   254     /// \param item The item.
   254     /// \param item The item.
   255     /// \param value The priority.
   255     /// \param value The priority.
   256     /// \pre \e item must be stored in the heap with priority at least \e value.
   256     /// \pre \e item must be stored in the heap with priority at least \e value.
   257     void decrease (Item item, const Prio& value) {
   257     void decrease (Item item, const Prio& value) {
   258       int i=_iim[item];
   258       int i=_iim[item];
   259 
   259       int p=_data[i].parent;
   260       if( _comp( value,_data[i].prio ) ) {
   260       _data[i].prio=value;
   261         _data[i].prio=value;
   261       
   262 
   262       while( p!=-1 && _comp(value, _data[p].prio) ) {
   263         int p_loc=_data[i].parent, loc=i;
   263         _data[i].name=_data[p].name;
   264         int parent, child, neighb;
   264         _data[i].prio=_data[p].prio;
   265 
   265         _data[p].name=item;
   266         while( -1!=p_loc && _comp(_data[loc].prio,_data[p_loc].prio) ) {
   266         _data[p].prio=value;
   267 
   267         _iim[_data[i].name]=i;
   268           // parent set for other loc_child
   268         i=p;
   269           child=_data[loc].child;
   269         p=_data[p].parent;
   270           while( -1!=child ) {
   270       }
   271             _data[child].parent=p_loc;
   271       _iim[item]=i;
   272             child=_data[child].right_neighbor;
   272       if ( _comp(value, _data[_min].prio) ) _min=i;
   273           }
       
   274 
       
   275           // parent set for other p_loc_child
       
   276           child=_data[p_loc].child;
       
   277           while( -1!=child ) {
       
   278             _data[child].parent=loc;
       
   279             child=_data[child].right_neighbor;
       
   280           }
       
   281 
       
   282           child=_data[p_loc].child;
       
   283           _data[p_loc].child=_data[loc].child;
       
   284           if( child==loc )
       
   285             child=p_loc;
       
   286           _data[loc].child=child;
       
   287 
       
   288           // left_neighb set for p_loc
       
   289           if( _data[loc].child!=p_loc ) {
       
   290             while( _data[child].right_neighbor!=loc )
       
   291               child=_data[child].right_neighbor;
       
   292             _data[child].right_neighbor=p_loc;
       
   293           }
       
   294 
       
   295           // left_neighb set for loc
       
   296           parent=_data[p_loc].parent;
       
   297           if( -1!=parent ) child=_data[parent].child;
       
   298           else child=_head;
       
   299 
       
   300           if( child!=p_loc ) {
       
   301             while( _data[child].right_neighbor!=p_loc )
       
   302               child=_data[child].right_neighbor;
       
   303             _data[child].right_neighbor=loc;
       
   304           }
       
   305 
       
   306           neighb=_data[p_loc].right_neighbor;
       
   307           _data[p_loc].right_neighbor=_data[loc].right_neighbor;
       
   308           _data[loc].right_neighbor=neighb;
       
   309 
       
   310           _data[p_loc].parent=loc;
       
   311           _data[loc].parent=parent;
       
   312 
       
   313           if( -1!=parent && _data[parent].child==p_loc )
       
   314             _data[parent].child=loc;
       
   315 
       
   316           /*if new parent will be the first root*/
       
   317           if( _head==p_loc )
       
   318             _head=loc;
       
   319 
       
   320           p_loc=_data[loc].parent;
       
   321         }
       
   322       }
       
   323       if( _comp(value,_data[_min].prio) ) {
       
   324         _min=i;
       
   325       }
       
   326     }
   273     }
   327 
   274 
   328     /// \brief Increase the priority of an item to the given value.
   275     /// \brief Increase the priority of an item to the given value.
   329     ///
   276     ///
   330     /// This function increases the priority of an item to the given value.
   277     /// This function increases the priority of an item to the given value.
   373         break;
   320         break;
   374       }
   321       }
   375     }
   322     }
   376 
   323 
   377   private:
   324   private:
       
   325     
       
   326     // Find the minimum of the roots
   378     int findMin() {
   327     int findMin() {
   379       int min_loc=-1, min_val;
   328       if( _head!=-1 ) {
   380       int x=_head;
   329         int min_loc=_head, min_val=_data[_head].prio;
   381       if( x!=-1 ) {
   330         for( int x=_data[_head].right_neighbor; x!=-1;
   382         min_val=_data[x].prio;
   331              x=_data[x].right_neighbor ) {
   383         min_loc=x;
       
   384         x=_data[x].right_neighbor;
       
   385 
       
   386         while( x!=-1 ) {
       
   387           if( _comp( _data[x].prio,min_val ) ) {
   332           if( _comp( _data[x].prio,min_val ) ) {
   388             min_val=_data[x].prio;
   333             min_val=_data[x].prio;
   389             min_loc=x;
   334             min_loc=x;
   390           }
   335           }
   391           x=_data[x].right_neighbor;
   336         }
   392         }
   337         return min_loc;
   393       }
   338       }
   394       return min_loc;
   339       else return -1;
   395     }
   340     }
   396 
   341 
       
   342     // Merge the heap with another heap starting at the given position
   397     void merge(int a) {
   343     void merge(int a) {
   398       interleave(a);
   344       if( _head==-1 || a==-1 ) return;
   399 
   345       if( _data[a].right_neighbor==-1 &&
       
   346           _data[a].degree<=_data[_head].degree ) {
       
   347         _data[a].right_neighbor=_head;
       
   348         _head=a;
       
   349       } else {
       
   350         interleave(a);
       
   351       }
       
   352       if( _data[_head].right_neighbor==-1 ) return;
       
   353       
   400       int x=_head;
   354       int x=_head;
   401       if( -1!=x ) {
   355       int x_prev=-1, x_next=_data[x].right_neighbor;
   402         int x_prev=-1, x_next=_data[x].right_neighbor;
   356       while( x_next!=-1 ) {
   403         while( -1!=x_next ) {
   357         if( _data[x].degree!=_data[x_next].degree ||
   404           if( _data[x].degree!=_data[x_next].degree || ( -1!=_data[x_next].right_neighbor && _data[_data[x_next].right_neighbor].degree==_data[x].degree ) ) {
   358             ( _data[x_next].right_neighbor!=-1 &&
   405             x_prev=x;
   359               _data[_data[x_next].right_neighbor].degree==_data[x].degree ) ) {
       
   360           x_prev=x;
       
   361           x=x_next;
       
   362         }
       
   363         else {
       
   364           if( _comp(_data[x_next].prio,_data[x].prio) ) {
       
   365             if( x_prev==-1 ) {
       
   366               _head=x_next;
       
   367             } else {
       
   368               _data[x_prev].right_neighbor=x_next;
       
   369             }
       
   370             fuse(x,x_next);
   406             x=x_next;
   371             x=x_next;
   407           }
   372           }
   408           else {
   373           else {
   409             if( _comp(_data[x].prio,_data[x_next].prio) ) {
   374             _data[x].right_neighbor=_data[x_next].right_neighbor;
   410               _data[x].right_neighbor=_data[x_next].right_neighbor;
   375             fuse(x_next,x);
   411               fuse(x_next,x);
       
   412             }
       
   413             else {
       
   414               if( -1==x_prev ) { _head=x_next; }
       
   415               else {
       
   416                 _data[x_prev].right_neighbor=x_next;
       
   417               }
       
   418               fuse(x,x_next);
       
   419               x=x_next;
       
   420             }
       
   421           }
   376           }
   422           x_next=_data[x].right_neighbor;
   377         }
   423         }
   378         x_next=_data[x].right_neighbor;
   424       }
   379       }
   425     }
   380     }
   426 
   381 
       
   382     // Interleave the elements of the given list into the list of the roots
   427     void interleave(int a) {
   383     void interleave(int a) {
   428       int other=-1, head_other=-1;
   384       int p=_head, q=a;
   429 
   385       int curr=_data.size();
   430       while( -1!=a || -1!=_head ) {
   386       _data.push_back(Store());
   431         if( -1==a ) {
   387       
   432           if( -1==head_other ) {
   388       while( p!=-1 || q!=-1 ) {
   433             head_other=_head;
   389         if( q==-1 || ( p!=-1 && _data[p].degree<_data[q].degree ) ) {
   434           }
   390           _data[curr].right_neighbor=p;
   435           else {
   391           curr=p;
   436             _data[other].right_neighbor=_head;
   392           p=_data[p].right_neighbor;
   437           }
       
   438           _head=-1;
       
   439         }
       
   440         else if( -1==_head ) {
       
   441           if( -1==head_other ) {
       
   442             head_other=a;
       
   443           }
       
   444           else {
       
   445             _data[other].right_neighbor=a;
       
   446           }
       
   447           a=-1;
       
   448         }
   393         }
   449         else {
   394         else {
   450           if( _data[a].degree<_data[_head].degree ) {
   395           _data[curr].right_neighbor=q;
   451             if( -1==head_other ) {
   396           curr=q;
   452               head_other=a;
   397           q=_data[q].right_neighbor;
   453             }
   398         }
   454             else {
   399       }
   455               _data[other].right_neighbor=a;
   400       
   456             }
   401       _head=_data.back().right_neighbor;
   457             other=a;
   402       _data.pop_back();
   458             a=_data[a].right_neighbor;
   403     }
   459           }
   404 
   460           else {
   405     // Lace node a under node b
   461             if( -1==head_other ) {
       
   462               head_other=_head;
       
   463             }
       
   464             else {
       
   465               _data[other].right_neighbor=_head;
       
   466             }
       
   467             other=_head;
       
   468             _head=_data[_head].right_neighbor;
       
   469           }
       
   470         }
       
   471       }
       
   472       _head=head_other;
       
   473     }
       
   474 
       
   475     // Lacing a under b
       
   476     void fuse(int a, int b) {
   406     void fuse(int a, int b) {
   477       _data[a].parent=b;
   407       _data[a].parent=b;
   478       _data[a].right_neighbor=_data[b].child;
   408       _data[a].right_neighbor=_data[b].child;
   479       _data[b].child=a;
   409       _data[b].child=a;
   480 
   410 
   481       ++_data[b].degree;
   411       ++_data[b].degree;
   482     }
   412     }
   483 
   413 
   484     // It is invoked only if a has siblings.
   414     // Unlace node a (if it has siblings)
   485     void unlace(int a) {
   415     void unlace(int a) {
   486       int neighb=_data[a].right_neighbor;
   416       int neighb=_data[a].right_neighbor;
   487       int other=_head;
   417       int other=_head;
   488 
   418 
   489       while( _data[other].right_neighbor!=a )
   419       while( _data[other].right_neighbor!=a )
   491       _data[other].right_neighbor=neighb;
   421       _data[other].right_neighbor=neighb;
   492     }
   422     }
   493 
   423 
   494   private:
   424   private:
   495 
   425 
   496     class store {
   426     class Store {
   497       friend class BinomHeap;
   427       friend class BinomHeap;
   498 
   428 
   499       Item name;
   429       Item name;
   500       int parent;
   430       int parent;
   501       int right_neighbor;
   431       int right_neighbor;
   502       int child;
   432       int child;
   503       int degree;
   433       int degree;
   504       bool in;
   434       bool in;
   505       Prio prio;
   435       Prio prio;
   506 
   436 
   507       store() : parent(-1), right_neighbor(-1), child(-1), degree(0), in(true) {}
   437       Store() : parent(-1), right_neighbor(-1), child(-1), degree(0),
       
   438         in(true) {}
   508     };
   439     };
   509   };
   440   };
   510 
   441 
   511 } //namespace lemon
   442 } //namespace lemon
   512 
   443