Changeset - r705:39a5b48bcace
« 704:7124b2
706:9314d9 »
gravatar
kpeter (Peter Kovacs)
kpeter@inf.elte.hu
Small improvements in heap implementations (#301)
0 2 0
default
2 files changed with 28 insertions and 32 deletions:
lemon/fourary_heap.h
10
8
lemon/pairing_heap.h
18
24
↑ Collapse diff ↑
lemon/fourary_heap.h
Show white space 6 line context
... ... 
@@ -167,10 +167,12 @@
167 167 
    void bubbleDown(int hole, Pair p, int length) {
168 
      int child = firstChild(hole);
169 
      while( child<length && length>1 ) {
170 
        child = findMin(child,length);
171 
        if( !less(_data[child], p) )
172 
          goto ok;
173 
        move(_data[child], hole);
174 
        hole = child;
175 
        child = firstChild(hole);
168 
      if( length>1 ) {
169 
        int child = firstChild(hole);
170 
        while( child<length ) {
171 
          child = findMin(child, length);
172 
          if( !less(_data[child], p) )
173 
            goto ok;
174 
          move(_data[child], hole);
175 
          hole = child;
176 
          child = firstChild(hole);
177 
        }
176 178 
      }
lemon/pairing_heap.h
Ignore white space 6 line context
... ... 
@@ -210,4 +210,4 @@
210 210 
    void pop() {
211 
      int TreeArray[_num_items];
212 
      int i=0, num_child=0, child_right = 0;
211 
      std::vector<int> trees;
212 
      int i=0, child_right = 0;
213 213 
      _data[_min].in=false;
... ... 
@@ -216,3 +216,3 @@
216 216 
        i=_data[_min].child;
217 
        TreeArray[num_child] = i;
217 
        trees.push_back(i);
218 218 
        _data[i].parent = -1;
... ... 
@@ -220,3 +220,2 @@
220 220 

			




	221
	
	
		
        ++num_child;


			




	222
	221
	
		
        int ch=-1;


			




	...
	...
	
		
@@ -225,4 +224,3 @@


			




	225
	224
	
		
          if( _data[ch].left_child && i==_data[ch].parent ) {


			




	226
	
	
		
            i=ch;


			




	227
	
	
		
            //break;


			




	
	225
	
		
            break;


			




	228
	226
	
		
          } else {


			




	...
	...
	
		
@@ -239,5 +237,4 @@


			




	239
	237
	
		
            _data[child_right].parent = -1;


			




	240
	
	
		
            TreeArray[num_child] = child_right;


			




	
	238
	
		
            trees.push_back(child_right);


			




	241
	239
	
		
            i = child_right;


			




	242
	
	
		
            ++num_child;


			




	243
	240
	
		
          }


			




	...
	...
	
		
@@ -245,11 +242,11 @@


			




	245
	242
	
		

			




	
	243
	
		
        int num_child = trees.size();


			




	246
	244
	
		
        int other;


			




	247
	245
	
		
        for( i=0; i<num_child-1; i+=2 ) {


			




	248
	
	
		
          if ( !_comp(_data[TreeArray[i]].prio,


			




	249
	
	
		
                     _data[TreeArray[i+1]].prio) ) {


			




	250
	
	
		
            other=TreeArray[i];


			




	251
	
	
		
            TreeArray[i]=TreeArray[i+1];


			




	252
	
	
		
            TreeArray[i+1]=other;


			




	
	246
	
		
          if ( !_comp(_data[trees[i]].prio, _data[trees[i+1]].prio) ) {


			




	
	247
	
		
            other=trees[i];


			




	
	248
	
		
            trees[i]=trees[i+1];


			




	
	249
	
		
            trees[i+1]=other;


			




	253
	250
	
		
          }


			




	254
	
	
		
          fuse( TreeArray[i], TreeArray[i+1] );


			




	
	251
	
		
          fuse( trees[i], trees[i+1] );


			




	255
	252
	
		
        }


			




	...
	...
	
		
@@ -258,15 +255,13 @@


			




	258
	255
	
		
        while(i>=2) {


			




	259
	
	
		
          if ( _comp(_data[TreeArray[i]].prio,


			




	260
	
	
		
                    _data[TreeArray[i-2]].prio) ) {


			




	261
	
	
		
            other=TreeArray[i];


			




	262
	
	
		
            TreeArray[i]=TreeArray[i-2];


			




	263
	
	
		
            TreeArray[i-2]=other;


			




	
	256
	
		
          if ( _comp(_data[trees[i]].prio, _data[trees[i-2]].prio) ) {


			




	
	257
	
		
            other=trees[i];


			




	
	258
	
		
            trees[i]=trees[i-2];


			




	
	259
	
		
            trees[i-2]=other;


			




	264
	260
	
		
          }


			




	265
	
	
		
          fuse( TreeArray[i-2], TreeArray[i] );


			




	
	261
	
		
          fuse( trees[i-2], trees[i] );


			




	266
	262
	
		
          i-=2;


			




	267
	263
	
		
        }


			




	268
	
	
		
        _min = TreeArray[0];


			




	
	264
	
		
        _min = trees[0];


			




	269
	265
	
		
      }


			




	270
	
	
		

			




	271
	
	
		
      if ( 0==num_child ) {


			




	
	266
	
		
      else {


			




	272
	267
	
		
        _min = _data[_min].child;


			




	...
	...
	
		
@@ -275,3 +270,2 @@


			




	275
	270
	
		
      if (_min >= 0) _data[_min].left_child = false;


			




	276
	
	
		

			




	277
	271
	
		
      --_num_items;


			




        

    






    
    



    


    

     
    
0 comments (0 inline)