COIN-OR::LEMON - Graph Library

Changeset 706:9314d9339475 in lemon-1.2 for lemon/kary_heap.h


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

Smarter bubbleDown() in K-ary heaps (#301)

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/kary_heap.h

    r704 r706  
    139139    }
    140140
    141     int findMin(const int child, const int length) {
    142       int min=child, i=1;
    143       while( i<K && child+i<length ) {
    144         if( less(_data[child+i], _data[min]) )
    145           min=child+i;
    146         ++i;
    147       }
    148       return min;
    149     }
    150 
    151141    void bubbleUp(int hole, Pair p) {
    152142      int par = parent(hole);
     
    162152      if( length>1 ) {
    163153        int child = firstChild(hole);
    164         while( child<length ) {
    165           child = findMin(child, length);
    166           if( !less(_data[child], p) )
     154        while( child+K<=length ) {
     155          int min=child;
     156          for (int i=1; i<K; ++i) {
     157            if( less(_data[child+i], _data[min]) )
     158              min=child+i;
     159          }
     160          if( !less(_data[min], p) )
    167161            goto ok;
    168           move(_data[child], hole);
    169           hole = child;
     162          move(_data[min], hole);
     163          hole = min;
    170164          child = firstChild(hole);
     165        }
     166        if ( child<length ) {
     167          int min = child;
     168          while (++child < length) {
     169            if( less(_data[child], _data[min]) )
     170              min=child;
     171          }
     172          if( less(_data[min], p) ) {
     173            move(_data[min], hole);
     174            hole = min;
     175          }
    171176        }
    172177      }
Note: See TracChangeset for help on using the changeset viewer.