Changeset 753:9314d9339475 in lemon for lemon/kary_heap.h

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)

File:

• lemon/kary_heap.h (modified) (2 diffs)

lemon/kary_heap.h

@@ -139 +139 @@
     }
 
-    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);
@@ -162 +152 @@
       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;
+          }
         }
       }