# HG changeset patch
# User Peter Kovacs <kpeter@inf.elte.hu>
# Date 2009-07-20 19:06:39
# Node ID 9314d9339475d4747dceb17b8f34d0bbc77d6b93
# Parent  39a5b48bcace4e67c679ae38cd9493203999171b

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

diff --git a/lemon/fourary_heap.h b/lemon/fourary_heap.h
--- a/lemon/fourary_heap.h
+++ b/lemon/fourary_heap.h
@@ -131,29 +131,6 @@
       return _comp(p1.second, p2.second);
     }
 
-    int findMin(const int child, const int length) {
-      int min=child;
-      if( child+3<length ) {
-        if( less(_data[child+3], _data[min]) )
-          min=child+3;
-        if( less(_data[child+2], _data[min]) )
-          min=child+2;
-        if( less(_data[child+1], _data[min]) )
-          min=child+1;
-      }
-      else if( child+2<length ) {
-        if( less(_data[child+2], _data[min]) )
-          min=child+2;
-        if( less(_data[child+1], _data[min]) )
-          min=child+1;
-      }
-      else if( child+1<length ) {
-        if( less(_data[child+1], _data[min]) )
-          min=child+1;
-      }
-      return min;
-    }
-
     void bubbleUp(int hole, Pair p) {
       int par = parent(hole);
       while( hole>0 && less(p,_data[par]) ) {
@@ -167,14 +144,26 @@
     void bubbleDown(int hole, Pair p, int length) {
       if( length>1 ) {
         int child = firstChild(hole);
-        while( child<length ) {
-          child = findMin(child, length);
-          if( !less(_data[child], p) )
+        while( child+3<length ) {
+          int min=child;
+          if( less(_data[++child], _data[min]) ) min=child;
+          if( less(_data[++child], _data[min]) ) min=child;
+          if( less(_data[++child], _data[min]) ) min=child;
+          if( !less(_data[min], p) )
             goto ok;
-          move(_data[child], hole);
-          hole = child;
+          move(_data[min], hole);
+          hole = min;
           child = firstChild(hole);
         }
+        if ( child<length ) {
+          int min = child;
+          if( ++child<length && less(_data[child], _data[min]) ) min=child;
+          if( ++child<length && less(_data[child], _data[min]) ) min=child;
+          if( less(_data[min], p) ) {
+            move(_data[min], hole);
+            hole = min;
+          }
+        }
       }
     ok:
       move(p, hole);
diff --git a/lemon/kary_heap.h b/lemon/kary_heap.h
--- a/lemon/kary_heap.h
+++ b/lemon/kary_heap.h
@@ -138,16 +138,6 @@
       return _comp(p1.second, p2.second);
     }
 
-    int findMin(const int child, const int length) {
-      int min=child, i=1;
-      while( i<K && child+i<length ) {
-        if( less(_data[child+i], _data[min]) )
-          min=child+i;
-        ++i;
-      }
-      return min;
-    }
-
     void bubbleUp(int hole, Pair p) {
       int par = parent(hole);
       while( hole>0 && less(p,_data[par]) ) {
@@ -161,14 +151,29 @@
     void bubbleDown(int hole, Pair p, int length) {
       if( length>1 ) {
         int child = firstChild(hole);
-        while( child<length ) {
-          child = findMin(child, length);
-          if( !less(_data[child], p) )
+        while( child+K<=length ) {
+          int min=child;
+          for (int i=1; i<K; ++i) {
+            if( less(_data[child+i], _data[min]) )
+              min=child+i;
+          }
+          if( !less(_data[min], p) )
             goto ok;
-          move(_data[child], hole);
-          hole = child;
+          move(_data[min], hole);
+          hole = min;
           child = firstChild(hole);
         }
+        if ( child<length ) {
+          int min = child;
+          while (++child < length) {
+            if( less(_data[child], _data[min]) )
+              min=child;
+          }
+          if( less(_data[min], p) ) {
+            move(_data[min], hole);
+            hole = min;
+          }
+        }
       }
     ok:
       move(p, hole);