COIN-OR::LEMON - Graph Library

Changeset 706:9314d9339475 in lemon-main


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

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

Location:
lemon
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • lemon/fourary_heap.h

    r705 r706  
    132132    }
    133133
    134     int findMin(const int child, const int length) {
    135       int min=child;
    136       if( child+3<length ) {
    137         if( less(_data[child+3], _data[min]) )
    138           min=child+3;
    139         if( less(_data[child+2], _data[min]) )
    140           min=child+2;
    141         if( less(_data[child+1], _data[min]) )
    142           min=child+1;
    143       }
    144       else if( child+2<length ) {
    145         if( less(_data[child+2], _data[min]) )
    146           min=child+2;
    147         if( less(_data[child+1], _data[min]) )
    148           min=child+1;
    149       }
    150       else if( child+1<length ) {
    151         if( less(_data[child+1], _data[min]) )
    152           min=child+1;
    153       }
    154       return min;
    155     }
    156 
    157134    void bubbleUp(int hole, Pair p) {
    158135      int par = parent(hole);
     
    168145      if( length>1 ) {
    169146        int child = firstChild(hole);
    170         while( child<length ) {
    171           child = findMin(child, length);
    172           if( !less(_data[child], p) )
     147        while( child+3<length ) {
     148          int min=child;
     149          if( less(_data[++child], _data[min]) ) min=child;
     150          if( less(_data[++child], _data[min]) ) min=child;
     151          if( less(_data[++child], _data[min]) ) min=child;
     152          if( !less(_data[min], p) )
    173153            goto ok;
    174           move(_data[child], hole);
    175           hole = child;
     154          move(_data[min], hole);
     155          hole = min;
    176156          child = firstChild(hole);
     157        }
     158        if ( child<length ) {
     159          int min = child;
     160          if( ++child<length && less(_data[child], _data[min]) ) min=child;
     161          if( ++child<length && less(_data[child], _data[min]) ) min=child;
     162          if( less(_data[min], p) ) {
     163            move(_data[min], hole);
     164            hole = min;
     165          }
    177166        }
    178167      }
  • 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.