Changeset 705:39a5b48bcace in lemon-main

Timestamp:

07/10/09 09:17:13 (15 years ago)

Author:

Peter Kovacs <kpeter@…>

Branch:

default

Phase:

public

Message:

Small improvements in heap implementations (#301)

Location:

lemon

Files:

• fourary_heap.h (modified) (1 diff)
• pairing_heap.h (modified) (2 diffs)

lemon/fourary_heap.h

@@ -166 +166 @@
 
     void bubbleDown(int hole, Pair p, int length) {
-      int child = firstChild(hole);
-      while( child<length && length>1 ) {
-        child = findMin(child,length);
-        if( !less(_data[child], p) )
-          goto ok;
-        move(_data[child], hole);
-        hole = child;
-        child = firstChild(hole);
+      if( length>1 ) {
+        int child = firstChild(hole);
+        while( child<length ) {
+          child = findMin(child, length);
+          if( !less(_data[child], p) )
+            goto ok;
+          move(_data[child], hole);
+          hole = child;
+          child = firstChild(hole);
+        }
       }
     ok:

lemon/pairing_heap.h

@@ -209 +209 @@
     /// \pre The heap must be non-empty.
     void pop() {
-      int TreeArray[_num_items];
-      int i=0, num_child=0, child_right = 0;
+      std::vector<int> trees;
+      int i=0, child_right = 0;
       _data[_min].in=false;
 
       if( -1!=_data[_min].child ) {
         i=_data[_min].child;
-        TreeArray[num_child] = i;
+        trees.push_back(i);
         _data[i].parent = -1;
         _data[_min].child = -1;
 
-        ++num_child;
         int ch=-1;
         while( _data[i].child!=-1 ) {
           ch=_data[i].child;
           if( _data[ch].left_child && i==_data[ch].parent ) {
-            i=ch;
-            //break;
+            break;
           } else {
             if( _data[ch].left_child ) {
@@ -238 +236 @@
             }
             _data[child_right].parent = -1;
-            TreeArray[num_child] = child_right;
+            trees.push_back(child_right);
             i = child_right;
-            ++num_child;
-          }
-        }
-
+          }
+        }
+
+        int num_child = trees.size();
         int other;
         for( i=0; i<num_child-1; i+=2 ) {
-          if ( !_comp(_data[TreeArray[i]].prio,
-                     _data[TreeArray[i+1]].prio) ) {
-            other=TreeArray[i];
-            TreeArray[i]=TreeArray[i+1];
-            TreeArray[i+1]=other;
-          }
-          fuse( TreeArray[i], TreeArray[i+1] );
+          if ( !_comp(_data[trees[i]].prio, _data[trees[i+1]].prio) ) {
+            other=trees[i];
+            trees[i]=trees[i+1];
+            trees[i+1]=other;
+          }
+          fuse( trees[i], trees[i+1] );
         }
 
         i = (0==(num_child % 2)) ? num_child-2 : num_child-1;
         while(i>=2) {
-          if ( _comp(_data[TreeArray[i]].prio,
-                    _data[TreeArray[i-2]].prio) ) {
-            other=TreeArray[i];
-            TreeArray[i]=TreeArray[i-2];
-            TreeArray[i-2]=other;
-          }
-          fuse( TreeArray[i-2], TreeArray[i] );
+          if ( _comp(_data[trees[i]].prio, _data[trees[i-2]].prio) ) {
+            other=trees[i];
+            trees[i]=trees[i-2];
+            trees[i-2]=other;
+          }
+          fuse( trees[i-2], trees[i] );
           i-=2;
         }
-        _min = TreeArray[0];
-      }
-
-      if ( 0==num_child ) {
+        _min = trees[0];
+      }
+      else {
         _min = _data[_min].child;
       }
 
       if (_min >= 0) _data[_min].left_child = false;
-
       --_num_items;
     }