Small improvements in heap implementations (#301)
authorPeter Kovacs <kpeter@inf.elte.hu>
Fri, 10 Jul 2009 09:17:13 +0200
changeset 75239a5b48bcace
parent 751 7124b2581f72
child 753 9314d9339475
Small improvements in heap implementations (#301)
lemon/fourary_heap.h
lemon/pairing_heap.h
     1.1 --- a/lemon/fourary_heap.h	Fri Jul 10 09:15:22 2009 +0200
     1.2 +++ b/lemon/fourary_heap.h	Fri Jul 10 09:17:13 2009 +0200
     1.3 @@ -165,14 +165,16 @@
     1.4      }
     1.5  
     1.6      void bubbleDown(int hole, Pair p, int length) {
     1.7 -      int child = firstChild(hole);
     1.8 -      while( child<length && length>1 ) {
     1.9 -        child = findMin(child,length);
    1.10 -        if( !less(_data[child], p) )
    1.11 -          goto ok;
    1.12 -        move(_data[child], hole);
    1.13 -        hole = child;
    1.14 -        child = firstChild(hole);
    1.15 +      if( length>1 ) {
    1.16 +        int child = firstChild(hole);
    1.17 +        while( child<length ) {
    1.18 +          child = findMin(child, length);
    1.19 +          if( !less(_data[child], p) )
    1.20 +            goto ok;
    1.21 +          move(_data[child], hole);
    1.22 +          hole = child;
    1.23 +          child = firstChild(hole);
    1.24 +        }
    1.25        }
    1.26      ok:
    1.27        move(p, hole);
     2.1 --- a/lemon/pairing_heap.h	Fri Jul 10 09:15:22 2009 +0200
     2.2 +++ b/lemon/pairing_heap.h	Fri Jul 10 09:17:13 2009 +0200
     2.3 @@ -208,23 +208,21 @@
     2.4      /// This function removes the item having minimum priority.
     2.5      /// \pre The heap must be non-empty.
     2.6      void pop() {
     2.7 -      int TreeArray[_num_items];
     2.8 -      int i=0, num_child=0, child_right = 0;
     2.9 +      std::vector<int> trees;
    2.10 +      int i=0, child_right = 0;
    2.11        _data[_min].in=false;
    2.12  
    2.13        if( -1!=_data[_min].child ) {
    2.14          i=_data[_min].child;
    2.15 -        TreeArray[num_child] = i;
    2.16 +        trees.push_back(i);
    2.17          _data[i].parent = -1;
    2.18          _data[_min].child = -1;
    2.19  
    2.20 -        ++num_child;
    2.21          int ch=-1;
    2.22          while( _data[i].child!=-1 ) {
    2.23            ch=_data[i].child;
    2.24            if( _data[ch].left_child && i==_data[ch].parent ) {
    2.25 -            i=ch;
    2.26 -            //break;
    2.27 +            break;
    2.28            } else {
    2.29              if( _data[ch].left_child ) {
    2.30                child_right=_data[ch].parent;
    2.31 @@ -237,43 +235,39 @@
    2.32                _data[i].degree=0;
    2.33              }
    2.34              _data[child_right].parent = -1;
    2.35 -            TreeArray[num_child] = child_right;
    2.36 +            trees.push_back(child_right);
    2.37              i = child_right;
    2.38 -            ++num_child;
    2.39            }
    2.40          }
    2.41  
    2.42 +        int num_child = trees.size();
    2.43          int other;
    2.44          for( i=0; i<num_child-1; i+=2 ) {
    2.45 -          if ( !_comp(_data[TreeArray[i]].prio,
    2.46 -                     _data[TreeArray[i+1]].prio) ) {
    2.47 -            other=TreeArray[i];
    2.48 -            TreeArray[i]=TreeArray[i+1];
    2.49 -            TreeArray[i+1]=other;
    2.50 +          if ( !_comp(_data[trees[i]].prio, _data[trees[i+1]].prio) ) {
    2.51 +            other=trees[i];
    2.52 +            trees[i]=trees[i+1];
    2.53 +            trees[i+1]=other;
    2.54            }
    2.55 -          fuse( TreeArray[i], TreeArray[i+1] );
    2.56 +          fuse( trees[i], trees[i+1] );
    2.57          }
    2.58  
    2.59          i = (0==(num_child % 2)) ? num_child-2 : num_child-1;
    2.60          while(i>=2) {
    2.61 -          if ( _comp(_data[TreeArray[i]].prio,
    2.62 -                    _data[TreeArray[i-2]].prio) ) {
    2.63 -            other=TreeArray[i];
    2.64 -            TreeArray[i]=TreeArray[i-2];
    2.65 -            TreeArray[i-2]=other;
    2.66 +          if ( _comp(_data[trees[i]].prio, _data[trees[i-2]].prio) ) {
    2.67 +            other=trees[i];
    2.68 +            trees[i]=trees[i-2];
    2.69 +            trees[i-2]=other;
    2.70            }
    2.71 -          fuse( TreeArray[i-2], TreeArray[i] );
    2.72 +          fuse( trees[i-2], trees[i] );
    2.73            i-=2;
    2.74          }
    2.75 -        _min = TreeArray[0];
    2.76 +        _min = trees[0];
    2.77        }
    2.78 -
    2.79 -      if ( 0==num_child ) {
    2.80 +      else {
    2.81          _min = _data[_min].child;
    2.82        }
    2.83  
    2.84        if (_min >= 0) _data[_min].left_child = false;
    2.85 -
    2.86        --_num_items;
    2.87      }
    2.88