1.1 --- a/lemon/fourary_heap.h	Fri Jul 10 09:17:13 2009 +0200
     1.2 +++ b/lemon/fourary_heap.h	Mon Jul 20 19:06:39 2009 +0200
     1.3 @@ -131,29 +131,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;
     1.9 -      if( child+3<length ) {
    1.10 -        if( less(_data[child+3], _data[min]) )
    1.11 -          min=child+3;
    1.12 -        if( less(_data[child+2], _data[min]) )
    1.13 -          min=child+2;
    1.14 -        if( less(_data[child+1], _data[min]) )
    1.15 -          min=child+1;
    1.16 -      }
    1.17 -      else if( child+2<length ) {
    1.18 -        if( less(_data[child+2], _data[min]) )
    1.19 -          min=child+2;
    1.20 -        if( less(_data[child+1], _data[min]) )
    1.21 -          min=child+1;
    1.22 -      }
    1.23 -      else if( child+1<length ) {
    1.24 -        if( less(_data[child+1], _data[min]) )
    1.25 -          min=child+1;
    1.26 -      }
    1.27 -      return min;
    1.28 -    }
    1.29 -
    1.30      void bubbleUp(int hole, Pair p) {
    1.31        int par = parent(hole);
    1.32        while( hole>0 && less(p,_data[par]) ) {
    1.33 @@ -167,14 +144,26 @@
    1.34      void bubbleDown(int hole, Pair p, int length) {
    1.35        if( length>1 ) {
    1.36          int child = firstChild(hole);
    1.37 -        while( child<length ) {
    1.38 -          child = findMin(child, length);
    1.39 -          if( !less(_data[child], p) )
    1.40 +        while( child+3<length ) {
    1.41 +          int min=child;
    1.42 +          if( less(_data[++child], _data[min]) ) min=child;
    1.43 +          if( less(_data[++child], _data[min]) ) min=child;
    1.44 +          if( less(_data[++child], _data[min]) ) min=child;
    1.45 +          if( !less(_data[min], p) )
    1.46              goto ok;
    1.47 -          move(_data[child], hole);
    1.48 -          hole = child;
    1.49 +          move(_data[min], hole);
    1.50 +          hole = min;
    1.51            child = firstChild(hole);
    1.52          }
    1.53 +        if ( child<length ) {
    1.54 +          int min = child;
    1.55 +          if( ++child<length && less(_data[child], _data[min]) ) min=child;
    1.56 +          if( ++child<length && less(_data[child], _data[min]) ) min=child;
    1.57 +          if( less(_data[min], p) ) {
    1.58 +            move(_data[min], hole);
    1.59 +            hole = min;
    1.60 +          }
    1.61 +        }
    1.62        }
    1.63      ok:
    1.64        move(p, hole);

     2.1 --- a/lemon/kary_heap.h	Fri Jul 10 09:17:13 2009 +0200
     2.2 +++ b/lemon/kary_heap.h	Mon Jul 20 19:06:39 2009 +0200
     2.3 @@ -138,16 +138,6 @@
     2.4        return _comp(p1.second, p2.second);
     2.5      }
     2.6  
     2.7 -    int findMin(const int child, const int length) {
     2.8 -      int min=child, i=1;
     2.9 -      while( i<K && child+i<length ) {
    2.10 -        if( less(_data[child+i], _data[min]) )
    2.11 -          min=child+i;
    2.12 -        ++i;
    2.13 -      }
    2.14 -      return min;
    2.15 -    }
    2.16 -
    2.17      void bubbleUp(int hole, Pair p) {
    2.18        int par = parent(hole);
    2.19        while( hole>0 && less(p,_data[par]) ) {
    2.20 @@ -161,14 +151,29 @@
    2.21      void bubbleDown(int hole, Pair p, int length) {
    2.22        if( length>1 ) {
    2.23          int child = firstChild(hole);
    2.24 -        while( child<length ) {
    2.25 -          child = findMin(child, length);
    2.26 -          if( !less(_data[child], p) )
    2.27 +        while( child+K<=length ) {
    2.28 +          int min=child;
    2.29 +          for (int i=1; i<K; ++i) {
    2.30 +            if( less(_data[child+i], _data[min]) )
    2.31 +              min=child+i;
    2.32 +          }
    2.33 +          if( !less(_data[min], p) )
    2.34              goto ok;
    2.35 -          move(_data[child], hole);
    2.36 -          hole = child;
    2.37 +          move(_data[min], hole);
    2.38 +          hole = min;
    2.39            child = firstChild(hole);
    2.40          }
    2.41 +        if ( child<length ) {
    2.42 +          int min = child;
    2.43 +          while (++child < length) {
    2.44 +            if( less(_data[child], _data[min]) )
    2.45 +              min=child;
    2.46 +          }
    2.47 +          if( less(_data[min], p) ) {
    2.48 +            move(_data[min], hole);
    2.49 +            hole = min;
    2.50 +          }
    2.51 +        }
    2.52        }
    2.53      ok:
    2.54        move(p, hole);