Much faster implementation for BinomHeap (#301)
authorPeter Kovacs <kpeter@inf.elte.hu>
Fri, 24 Jul 2009 01:07:45 +0200
changeset 7073887d6f994d7
parent 706 9314d9339475
child 708 5d313b76f323
Much faster implementation for BinomHeap (#301)
lemon/binom_heap.h
     1.1 --- a/lemon/binom_heap.h	Mon Jul 20 19:06:39 2009 +0200
     1.2 +++ b/lemon/binom_heap.h	Fri Jul 24 01:07:45 2009 +0200
     1.3 @@ -79,9 +79,9 @@
     1.4      };
     1.5  
     1.6    private:
     1.7 -    class store;
     1.8 +    class Store;
     1.9  
    1.10 -    std::vector<store> _data;
    1.11 +    std::vector<Store> _data;
    1.12      int _min, _head;
    1.13      ItemIntMap &_iim;
    1.14      Compare _comp;
    1.15 @@ -156,8 +156,9 @@
    1.16        if ( i<0 ) {
    1.17          int s=_data.size();
    1.18          _iim.set( item,s );
    1.19 -        store st;
    1.20 +        Store st;
    1.21          st.name=item;
    1.22 +        st.prio=value;
    1.23          _data.push_back(st);
    1.24          i=s;
    1.25        }
    1.26 @@ -165,14 +166,16 @@
    1.27          _data[i].parent=_data[i].right_neighbor=_data[i].child=-1;
    1.28          _data[i].degree=0;
    1.29          _data[i].in=true;
    1.30 +        _data[i].prio=value;
    1.31        }
    1.32 -      _data[i].prio=value;
    1.33  
    1.34 -      if( 0==_num_items ) { _head=i; _min=i; }
    1.35 -      else { merge(i); }
    1.36 -
    1.37 -      _min = findMin();
    1.38 -
    1.39 +      if( 0==_num_items ) {
    1.40 +        _head=i;
    1.41 +        _min=i;
    1.42 +      } else {
    1.43 +        merge(i);
    1.44 +        if( _comp(_data[i].prio, _data[_min].prio) ) _min=i;
    1.45 +      }
    1.46        ++_num_items;
    1.47      }
    1.48  
    1.49 @@ -208,26 +211,23 @@
    1.50        if ( _data[_min].child!=-1 ) {
    1.51          int child=_data[_min].child;
    1.52          int neighb;
    1.53 -        int prev=-1;
    1.54          while( child!=-1 ) {
    1.55            neighb=_data[child].right_neighbor;
    1.56            _data[child].parent=-1;
    1.57 -          _data[child].right_neighbor=prev;
    1.58 +          _data[child].right_neighbor=head_child;
    1.59            head_child=child;
    1.60 -          prev=child;
    1.61            child=neighb;
    1.62          }
    1.63        }
    1.64  
    1.65 -      // The first case is that there are only one root.
    1.66 -      if ( -1==_data[_head].right_neighbor ) {
    1.67 +      if ( _data[_head].right_neighbor==-1 ) {
    1.68 +        // there was only one root
    1.69          _head=head_child;
    1.70        }
    1.71 -      // The case where there are more roots.
    1.72        else {
    1.73 +        // there were more roots
    1.74          if( _head!=_min )  { unlace(_min); }
    1.75          else { _head=_data[_head].right_neighbor; }
    1.76 -
    1.77          merge(head_child);
    1.78        }
    1.79        _min=findMin();
    1.80 @@ -256,73 +256,20 @@
    1.81      /// \pre \e item must be stored in the heap with priority at least \e value.
    1.82      void decrease (Item item, const Prio& value) {
    1.83        int i=_iim[item];
    1.84 -
    1.85 -      if( _comp( value,_data[i].prio ) ) {
    1.86 -        _data[i].prio=value;
    1.87 -
    1.88 -        int p_loc=_data[i].parent, loc=i;
    1.89 -        int parent, child, neighb;
    1.90 -
    1.91 -        while( -1!=p_loc && _comp(_data[loc].prio,_data[p_loc].prio) ) {
    1.92 -
    1.93 -          // parent set for other loc_child
    1.94 -          child=_data[loc].child;
    1.95 -          while( -1!=child ) {
    1.96 -            _data[child].parent=p_loc;
    1.97 -            child=_data[child].right_neighbor;
    1.98 -          }
    1.99 -
   1.100 -          // parent set for other p_loc_child
   1.101 -          child=_data[p_loc].child;
   1.102 -          while( -1!=child ) {
   1.103 -            _data[child].parent=loc;
   1.104 -            child=_data[child].right_neighbor;
   1.105 -          }
   1.106 -
   1.107 -          child=_data[p_loc].child;
   1.108 -          _data[p_loc].child=_data[loc].child;
   1.109 -          if( child==loc )
   1.110 -            child=p_loc;
   1.111 -          _data[loc].child=child;
   1.112 -
   1.113 -          // left_neighb set for p_loc
   1.114 -          if( _data[loc].child!=p_loc ) {
   1.115 -            while( _data[child].right_neighbor!=loc )
   1.116 -              child=_data[child].right_neighbor;
   1.117 -            _data[child].right_neighbor=p_loc;
   1.118 -          }
   1.119 -
   1.120 -          // left_neighb set for loc
   1.121 -          parent=_data[p_loc].parent;
   1.122 -          if( -1!=parent ) child=_data[parent].child;
   1.123 -          else child=_head;
   1.124 -
   1.125 -          if( child!=p_loc ) {
   1.126 -            while( _data[child].right_neighbor!=p_loc )
   1.127 -              child=_data[child].right_neighbor;
   1.128 -            _data[child].right_neighbor=loc;
   1.129 -          }
   1.130 -
   1.131 -          neighb=_data[p_loc].right_neighbor;
   1.132 -          _data[p_loc].right_neighbor=_data[loc].right_neighbor;
   1.133 -          _data[loc].right_neighbor=neighb;
   1.134 -
   1.135 -          _data[p_loc].parent=loc;
   1.136 -          _data[loc].parent=parent;
   1.137 -
   1.138 -          if( -1!=parent && _data[parent].child==p_loc )
   1.139 -            _data[parent].child=loc;
   1.140 -
   1.141 -          /*if new parent will be the first root*/
   1.142 -          if( _head==p_loc )
   1.143 -            _head=loc;
   1.144 -
   1.145 -          p_loc=_data[loc].parent;
   1.146 -        }
   1.147 +      int p=_data[i].parent;
   1.148 +      _data[i].prio=value;
   1.149 +      
   1.150 +      while( p!=-1 && _comp(value, _data[p].prio) ) {
   1.151 +        _data[i].name=_data[p].name;
   1.152 +        _data[i].prio=_data[p].prio;
   1.153 +        _data[p].name=item;
   1.154 +        _data[p].prio=value;
   1.155 +        _iim[_data[i].name]=i;
   1.156 +        i=p;
   1.157 +        p=_data[p].parent;
   1.158        }
   1.159 -      if( _comp(value,_data[_min].prio) ) {
   1.160 -        _min=i;
   1.161 -      }
   1.162 +      _iim[item]=i;
   1.163 +      if ( _comp(value, _data[_min].prio) ) _min=i;
   1.164      }
   1.165  
   1.166      /// \brief Increase the priority of an item to the given value.
   1.167 @@ -375,104 +322,87 @@
   1.168      }
   1.169  
   1.170    private:
   1.171 +    
   1.172 +    // Find the minimum of the roots
   1.173      int findMin() {
   1.174 -      int min_loc=-1, min_val;
   1.175 -      int x=_head;
   1.176 -      if( x!=-1 ) {
   1.177 -        min_val=_data[x].prio;
   1.178 -        min_loc=x;
   1.179 -        x=_data[x].right_neighbor;
   1.180 -
   1.181 -        while( x!=-1 ) {
   1.182 +      if( _head!=-1 ) {
   1.183 +        int min_loc=_head, min_val=_data[_head].prio;
   1.184 +        for( int x=_data[_head].right_neighbor; x!=-1;
   1.185 +             x=_data[x].right_neighbor ) {
   1.186            if( _comp( _data[x].prio,min_val ) ) {
   1.187              min_val=_data[x].prio;
   1.188              min_loc=x;
   1.189            }
   1.190 -          x=_data[x].right_neighbor;
   1.191          }
   1.192 +        return min_loc;
   1.193        }
   1.194 -      return min_loc;
   1.195 +      else return -1;
   1.196      }
   1.197  
   1.198 +    // Merge the heap with another heap starting at the given position
   1.199      void merge(int a) {
   1.200 -      interleave(a);
   1.201 -
   1.202 +      if( _head==-1 || a==-1 ) return;
   1.203 +      if( _data[a].right_neighbor==-1 &&
   1.204 +          _data[a].degree<=_data[_head].degree ) {
   1.205 +        _data[a].right_neighbor=_head;
   1.206 +        _head=a;
   1.207 +      } else {
   1.208 +        interleave(a);
   1.209 +      }
   1.210 +      if( _data[_head].right_neighbor==-1 ) return;
   1.211 +      
   1.212        int x=_head;
   1.213 -      if( -1!=x ) {
   1.214 -        int x_prev=-1, x_next=_data[x].right_neighbor;
   1.215 -        while( -1!=x_next ) {
   1.216 -          if( _data[x].degree!=_data[x_next].degree || ( -1!=_data[x_next].right_neighbor && _data[_data[x_next].right_neighbor].degree==_data[x].degree ) ) {
   1.217 -            x_prev=x;
   1.218 +      int x_prev=-1, x_next=_data[x].right_neighbor;
   1.219 +      while( x_next!=-1 ) {
   1.220 +        if( _data[x].degree!=_data[x_next].degree ||
   1.221 +            ( _data[x_next].right_neighbor!=-1 &&
   1.222 +              _data[_data[x_next].right_neighbor].degree==_data[x].degree ) ) {
   1.223 +          x_prev=x;
   1.224 +          x=x_next;
   1.225 +        }
   1.226 +        else {
   1.227 +          if( _comp(_data[x_next].prio,_data[x].prio) ) {
   1.228 +            if( x_prev==-1 ) {
   1.229 +              _head=x_next;
   1.230 +            } else {
   1.231 +              _data[x_prev].right_neighbor=x_next;
   1.232 +            }
   1.233 +            fuse(x,x_next);
   1.234              x=x_next;
   1.235            }
   1.236            else {
   1.237 -            if( _comp(_data[x].prio,_data[x_next].prio) ) {
   1.238 -              _data[x].right_neighbor=_data[x_next].right_neighbor;
   1.239 -              fuse(x_next,x);
   1.240 -            }
   1.241 -            else {
   1.242 -              if( -1==x_prev ) { _head=x_next; }
   1.243 -              else {
   1.244 -                _data[x_prev].right_neighbor=x_next;
   1.245 -              }
   1.246 -              fuse(x,x_next);
   1.247 -              x=x_next;
   1.248 -            }
   1.249 +            _data[x].right_neighbor=_data[x_next].right_neighbor;
   1.250 +            fuse(x_next,x);
   1.251            }
   1.252 -          x_next=_data[x].right_neighbor;
   1.253          }
   1.254 +        x_next=_data[x].right_neighbor;
   1.255        }
   1.256      }
   1.257  
   1.258 +    // Interleave the elements of the given list into the list of the roots
   1.259      void interleave(int a) {
   1.260 -      int other=-1, head_other=-1;
   1.261 -
   1.262 -      while( -1!=a || -1!=_head ) {
   1.263 -        if( -1==a ) {
   1.264 -          if( -1==head_other ) {
   1.265 -            head_other=_head;
   1.266 -          }
   1.267 -          else {
   1.268 -            _data[other].right_neighbor=_head;
   1.269 -          }
   1.270 -          _head=-1;
   1.271 -        }
   1.272 -        else if( -1==_head ) {
   1.273 -          if( -1==head_other ) {
   1.274 -            head_other=a;
   1.275 -          }
   1.276 -          else {
   1.277 -            _data[other].right_neighbor=a;
   1.278 -          }
   1.279 -          a=-1;
   1.280 +      int p=_head, q=a;
   1.281 +      int curr=_data.size();
   1.282 +      _data.push_back(Store());
   1.283 +      
   1.284 +      while( p!=-1 || q!=-1 ) {
   1.285 +        if( q==-1 || ( p!=-1 && _data[p].degree<_data[q].degree ) ) {
   1.286 +          _data[curr].right_neighbor=p;
   1.287 +          curr=p;
   1.288 +          p=_data[p].right_neighbor;
   1.289          }
   1.290          else {
   1.291 -          if( _data[a].degree<_data[_head].degree ) {
   1.292 -            if( -1==head_other ) {
   1.293 -              head_other=a;
   1.294 -            }
   1.295 -            else {
   1.296 -              _data[other].right_neighbor=a;
   1.297 -            }
   1.298 -            other=a;
   1.299 -            a=_data[a].right_neighbor;
   1.300 -          }
   1.301 -          else {
   1.302 -            if( -1==head_other ) {
   1.303 -              head_other=_head;
   1.304 -            }
   1.305 -            else {
   1.306 -              _data[other].right_neighbor=_head;
   1.307 -            }
   1.308 -            other=_head;
   1.309 -            _head=_data[_head].right_neighbor;
   1.310 -          }
   1.311 +          _data[curr].right_neighbor=q;
   1.312 +          curr=q;
   1.313 +          q=_data[q].right_neighbor;
   1.314          }
   1.315        }
   1.316 -      _head=head_other;
   1.317 +      
   1.318 +      _head=_data.back().right_neighbor;
   1.319 +      _data.pop_back();
   1.320      }
   1.321  
   1.322 -    // Lacing a under b
   1.323 +    // Lace node a under node b
   1.324      void fuse(int a, int b) {
   1.325        _data[a].parent=b;
   1.326        _data[a].right_neighbor=_data[b].child;
   1.327 @@ -481,7 +411,7 @@
   1.328        ++_data[b].degree;
   1.329      }
   1.330  
   1.331 -    // It is invoked only if a has siblings.
   1.332 +    // Unlace node a (if it has siblings)
   1.333      void unlace(int a) {
   1.334        int neighb=_data[a].right_neighbor;
   1.335        int other=_head;
   1.336 @@ -493,7 +423,7 @@
   1.337  
   1.338    private:
   1.339  
   1.340 -    class store {
   1.341 +    class Store {
   1.342        friend class BinomHeap;
   1.343  
   1.344        Item name;
   1.345 @@ -504,7 +434,8 @@
   1.346        bool in;
   1.347        Prio prio;
   1.348  
   1.349 -      store() : parent(-1), right_neighbor(-1), child(-1), degree(0), in(true) {}
   1.350 +      Store() : parent(-1), right_neighbor(-1), child(-1), degree(0),
   1.351 +        in(true) {}
   1.352      };
   1.353    };
   1.354