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);