lemon/binomial_heap.h
changeset 905 de428ebb47ab
parent 855 65a0521e744e
equal deleted inserted replaced
0:b036ebcfd839 1:40099925394f
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library.
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     4  *
     5  * Copyright (C) 2003-2009
     5  * Copyright (C) 2003-2010
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     8  *
     9  * Permission to use, modify and distribute this software is granted
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    10  * provided that this copyright notice appears in all copies. For
   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       int p=_data[i].parent;
   259       int p=_data[i].parent;
   260       _data[i].prio=value;
   260       _data[i].prio=value;
   261       
   261 
   262       while( p!=-1 && _comp(value, _data[p].prio) ) {
   262       while( p!=-1 && _comp(value, _data[p].prio) ) {
   263         _data[i].name=_data[p].name;
   263         _data[i].name=_data[p].name;
   264         _data[i].prio=_data[p].prio;
   264         _data[i].prio=_data[p].prio;
   265         _data[p].name=item;
   265         _data[p].name=item;
   266         _data[p].prio=value;
   266         _data[p].prio=value;
   320         break;
   320         break;
   321       }
   321       }
   322     }
   322     }
   323 
   323 
   324   private:
   324   private:
   325     
   325 
   326     // Find the minimum of the roots
   326     // Find the minimum of the roots
   327     int findMin() {
   327     int findMin() {
   328       if( _head!=-1 ) {
   328       if( _head!=-1 ) {
   329         int min_loc=_head, min_val=_data[_head].prio;
   329         int min_loc=_head, min_val=_data[_head].prio;
   330         for( int x=_data[_head].right_neighbor; x!=-1;
   330         for( int x=_data[_head].right_neighbor; x!=-1;
   348         _head=a;
   348         _head=a;
   349       } else {
   349       } else {
   350         interleave(a);
   350         interleave(a);
   351       }
   351       }
   352       if( _data[_head].right_neighbor==-1 ) return;
   352       if( _data[_head].right_neighbor==-1 ) return;
   353       
   353 
   354       int x=_head;
   354       int x=_head;
   355       int x_prev=-1, x_next=_data[x].right_neighbor;
   355       int x_prev=-1, x_next=_data[x].right_neighbor;
   356       while( x_next!=-1 ) {
   356       while( x_next!=-1 ) {
   357         if( _data[x].degree!=_data[x_next].degree ||
   357         if( _data[x].degree!=_data[x_next].degree ||
   358             ( _data[x_next].right_neighbor!=-1 &&
   358             ( _data[x_next].right_neighbor!=-1 &&
   382     // Interleave the elements of the given list into the list of the roots
   382     // Interleave the elements of the given list into the list of the roots
   383     void interleave(int a) {
   383     void interleave(int a) {
   384       int p=_head, q=a;
   384       int p=_head, q=a;
   385       int curr=_data.size();
   385       int curr=_data.size();
   386       _data.push_back(Store());
   386       _data.push_back(Store());
   387       
   387 
   388       while( p!=-1 || q!=-1 ) {
   388       while( p!=-1 || q!=-1 ) {
   389         if( q==-1 || ( p!=-1 && _data[p].degree<_data[q].degree ) ) {
   389         if( q==-1 || ( p!=-1 && _data[p].degree<_data[q].degree ) ) {
   390           _data[curr].right_neighbor=p;
   390           _data[curr].right_neighbor=p;
   391           curr=p;
   391           curr=p;
   392           p=_data[p].right_neighbor;
   392           p=_data[p].right_neighbor;
   395           _data[curr].right_neighbor=q;
   395           _data[curr].right_neighbor=q;
   396           curr=q;
   396           curr=q;
   397           q=_data[q].right_neighbor;
   397           q=_data[q].right_neighbor;
   398         }
   398         }
   399       }
   399       }
   400       
   400 
   401       _head=_data.back().right_neighbor;
   401       _head=_data.back().right_neighbor;
   402       _data.pop_back();
   402       _data.pop_back();
   403     }
   403     }
   404 
   404 
   405     // Lace node a under node b
   405     // Lace node a under node b