Changeset 706:9314d9339475 in lemon-main

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)

Location:

lemon

Files:

• fourary_heap.h (modified) (2 diffs)
• kary_heap.h (modified) (2 diffs)

lemon/fourary_heap.h

@@ -132 +132 @@
     }
 
-    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);
@@ -168 +145 @@
       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;
+          }
         }
       }

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;
+          }
         }
       }