1.1 --- a/lemon/kary_heap.h	Fri Jul 10 09:17:13 2009 +0200
     1.2 +++ b/lemon/kary_heap.h	Mon Jul 20 19:06:39 2009 +0200
     1.3 @@ -138,16 +138,6 @@
     1.4        return _comp(p1.second, p2.second);
     1.5      }
     1.6  
     1.7 -    int findMin(const int child, const int length) {
     1.8 -      int min=child, i=1;
     1.9 -      while( i<K && child+i<length ) {
    1.10 -        if( less(_data[child+i], _data[min]) )
    1.11 -          min=child+i;
    1.12 -        ++i;
    1.13 -      }
    1.14 -      return min;
    1.15 -    }
    1.16 -
    1.17      void bubbleUp(int hole, Pair p) {
    1.18        int par = parent(hole);
    1.19        while( hole>0 && less(p,_data[par]) ) {
    1.20 @@ -161,14 +151,29 @@
    1.21      void bubbleDown(int hole, Pair p, int length) {
    1.22        if( length>1 ) {
    1.23          int child = firstChild(hole);
    1.24 -        while( child<length ) {
    1.25 -          child = findMin(child, length);
    1.26 -          if( !less(_data[child], p) )
    1.27 +        while( child+K<=length ) {
    1.28 +          int min=child;
    1.29 +          for (int i=1; i<K; ++i) {
    1.30 +            if( less(_data[child+i], _data[min]) )
    1.31 +              min=child+i;
    1.32 +          }
    1.33 +          if( !less(_data[min], p) )
    1.34              goto ok;
    1.35 -          move(_data[child], hole);
    1.36 -          hole = child;
    1.37 +          move(_data[min], hole);
    1.38 +          hole = min;
    1.39            child = firstChild(hole);
    1.40          }
    1.41 +        if ( child<length ) {
    1.42 +          int min = child;
    1.43 +          while (++child < length) {
    1.44 +            if( less(_data[child], _data[min]) )
    1.45 +              min=child;
    1.46 +          }
    1.47 +          if( less(_data[min], p) ) {
    1.48 +            move(_data[min], hole);
    1.49 +            hole = min;
    1.50 +          }
    1.51 +        }
    1.52        }
    1.53      ok:
    1.54        move(p, hole);