1.1 --- a/lemon/pairing_heap.h Fri Jul 10 09:15:22 2009 +0200
1.2 +++ b/lemon/pairing_heap.h Fri Jul 10 09:17:13 2009 +0200
1.3 @@ -208,23 +208,21 @@
1.4 /// This function removes the item having minimum priority.
1.5 /// \pre The heap must be non-empty.
1.6 void pop() {
1.7 - int TreeArray[_num_items];
1.8 - int i=0, num_child=0, child_right = 0;
1.9 + std::vector<int> trees;
1.10 + int i=0, child_right = 0;
1.11 _data[_min].in=false;
1.12
1.13 if( -1!=_data[_min].child ) {
1.14 i=_data[_min].child;
1.15 - TreeArray[num_child] = i;
1.16 + trees.push_back(i);
1.17 _data[i].parent = -1;
1.18 _data[_min].child = -1;
1.19
1.20 - ++num_child;
1.21 int ch=-1;
1.22 while( _data[i].child!=-1 ) {
1.23 ch=_data[i].child;
1.24 if( _data[ch].left_child && i==_data[ch].parent ) {
1.25 - i=ch;
1.26 - //break;
1.27 + break;
1.28 } else {
1.29 if( _data[ch].left_child ) {
1.30 child_right=_data[ch].parent;
1.31 @@ -237,43 +235,39 @@
1.32 _data[i].degree=0;
1.33 }
1.34 _data[child_right].parent = -1;
1.35 - TreeArray[num_child] = child_right;
1.36 + trees.push_back(child_right);
1.37 i = child_right;
1.38 - ++num_child;
1.39 }
1.40 }
1.41
1.42 + int num_child = trees.size();
1.43 int other;
1.44 for( i=0; i<num_child-1; i+=2 ) {
1.45 - if ( !_comp(_data[TreeArray[i]].prio,
1.46 - _data[TreeArray[i+1]].prio) ) {
1.47 - other=TreeArray[i];
1.48 - TreeArray[i]=TreeArray[i+1];
1.49 - TreeArray[i+1]=other;
1.50 + if ( !_comp(_data[trees[i]].prio, _data[trees[i+1]].prio) ) {
1.51 + other=trees[i];
1.52 + trees[i]=trees[i+1];
1.53 + trees[i+1]=other;
1.54 }
1.55 - fuse( TreeArray[i], TreeArray[i+1] );
1.56 + fuse( trees[i], trees[i+1] );
1.57 }
1.58
1.59 i = (0==(num_child % 2)) ? num_child-2 : num_child-1;
1.60 while(i>=2) {
1.61 - if ( _comp(_data[TreeArray[i]].prio,
1.62 - _data[TreeArray[i-2]].prio) ) {
1.63 - other=TreeArray[i];
1.64 - TreeArray[i]=TreeArray[i-2];
1.65 - TreeArray[i-2]=other;
1.66 + if ( _comp(_data[trees[i]].prio, _data[trees[i-2]].prio) ) {
1.67 + other=trees[i];
1.68 + trees[i]=trees[i-2];
1.69 + trees[i-2]=other;
1.70 }
1.71 - fuse( TreeArray[i-2], TreeArray[i] );
1.72 + fuse( trees[i-2], trees[i] );
1.73 i-=2;
1.74 }
1.75 - _min = TreeArray[0];
1.76 + _min = trees[0];
1.77 }
1.78 -
1.79 - if ( 0==num_child ) {
1.80 + else {
1.81 _min = _data[_min].child;
1.82 }
1.83
1.84 if (_min >= 0) _data[_min].left_child = false;
1.85 -
1.86 --_num_items;
1.87 }
1.88