COIN-OR::LEMON - Graph Library

Changeset 705:39a5b48bcace in lemon-main


Ignore:
Timestamp:
07/10/09 09:17:13 (10 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

Small improvements in heap implementations (#301)

Location:
lemon
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • lemon/fourary_heap.h

    r703 r705  
    166166
    167167    void bubbleDown(int hole, Pair p, int length) {
    168       int child = firstChild(hole);
    169       while( child<length && length>1 ) {
    170         child = findMin(child,length);
    171         if( !less(_data[child], p) )
    172           goto ok;
    173         move(_data[child], hole);
    174         hole = child;
    175         child = firstChild(hole);
     168      if( length>1 ) {
     169        int child = firstChild(hole);
     170        while( child<length ) {
     171          child = findMin(child, length);
     172          if( !less(_data[child], p) )
     173            goto ok;
     174          move(_data[child], hole);
     175          hole = child;
     176          child = firstChild(hole);
     177        }
    176178      }
    177179    ok:
  • lemon/pairing_heap.h

    r703 r705  
    209209    /// \pre The heap must be non-empty.
    210210    void pop() {
    211       int TreeArray[_num_items];
    212       int i=0, num_child=0, child_right = 0;
     211      std::vector<int> trees;
     212      int i=0, child_right = 0;
    213213      _data[_min].in=false;
    214214
    215215      if( -1!=_data[_min].child ) {
    216216        i=_data[_min].child;
    217         TreeArray[num_child] = i;
     217        trees.push_back(i);
    218218        _data[i].parent = -1;
    219219        _data[_min].child = -1;
    220220
    221         ++num_child;
    222221        int ch=-1;
    223222        while( _data[i].child!=-1 ) {
    224223          ch=_data[i].child;
    225224          if( _data[ch].left_child && i==_data[ch].parent ) {
    226             i=ch;
    227             //break;
     225            break;
    228226          } else {
    229227            if( _data[ch].left_child ) {
     
    238236            }
    239237            _data[child_right].parent = -1;
    240             TreeArray[num_child] = child_right;
     238            trees.push_back(child_right);
    241239            i = child_right;
    242             ++num_child;
    243           }
    244         }
    245 
     240          }
     241        }
     242
     243        int num_child = trees.size();
    246244        int other;
    247245        for( i=0; i<num_child-1; i+=2 ) {
    248           if ( !_comp(_data[TreeArray[i]].prio,
    249                      _data[TreeArray[i+1]].prio) ) {
    250             other=TreeArray[i];
    251             TreeArray[i]=TreeArray[i+1];
    252             TreeArray[i+1]=other;
    253           }
    254           fuse( TreeArray[i], TreeArray[i+1] );
     246          if ( !_comp(_data[trees[i]].prio, _data[trees[i+1]].prio) ) {
     247            other=trees[i];
     248            trees[i]=trees[i+1];
     249            trees[i+1]=other;
     250          }
     251          fuse( trees[i], trees[i+1] );
    255252        }
    256253
    257254        i = (0==(num_child % 2)) ? num_child-2 : num_child-1;
    258255        while(i>=2) {
    259           if ( _comp(_data[TreeArray[i]].prio,
    260                     _data[TreeArray[i-2]].prio) ) {
    261             other=TreeArray[i];
    262             TreeArray[i]=TreeArray[i-2];
    263             TreeArray[i-2]=other;
    264           }
    265           fuse( TreeArray[i-2], TreeArray[i] );
     256          if ( _comp(_data[trees[i]].prio, _data[trees[i-2]].prio) ) {
     257            other=trees[i];
     258            trees[i]=trees[i-2];
     259            trees[i-2]=other;
     260          }
     261          fuse( trees[i-2], trees[i] );
    266262          i-=2;
    267263        }
    268         _min = TreeArray[0];
    269       }
    270 
    271       if ( 0==num_child ) {
     264        _min = trees[0];
     265      }
     266      else {
    272267        _min = _data[_min].child;
    273268      }
    274269
    275270      if (_min >= 0) _data[_min].left_child = false;
    276 
    277271      --_num_items;
    278272    }
Note: See TracChangeset for help on using the changeset viewer.