Changeset - r706:9314d9339475
« 705:39a5b4
707:3887d6 »
gravatar
kpeter (Peter Kovacs)
kpeter@inf.elte.hu
Smarter bubbleDown() in K-ary heaps (#301)
0 2 0
default
2 files changed with 37 insertions and 43 deletions:
lemon/fourary_heap.h
17
28
lemon/kary_heap.h
20
15
↑ Collapse diff ↑
lemon/fourary_heap.h
Ignore white space 6 line context
... ... 
@@ -133,25 +133,2 @@
133 133 

			




	134
	
	
		
    int findMin(const int child, const int length) {


			




	135
	
	
		
      int min=child;


			




	136
	
	
		
      if( child+3<length ) {


			




	137
	
	
		
        if( less(_data[child+3], _data[min]) )


			




	138
	
	
		
          min=child+3;


			




	139
	
	
		
        if( less(_data[child+2], _data[min]) )


			




	140
	
	
		
          min=child+2;


			




	141
	
	
		
        if( less(_data[child+1], _data[min]) )


			




	142
	
	
		
          min=child+1;


			




	143
	
	
		
      }


			




	144
	
	
		
      else if( child+2<length ) {


			




	145
	
	
		
        if( less(_data[child+2], _data[min]) )


			




	146
	
	
		
          min=child+2;


			




	147
	
	
		
        if( less(_data[child+1], _data[min]) )


			




	148
	
	
		
          min=child+1;


			




	149
	
	
		
      }


			




	150
	
	
		
      else if( child+1<length ) {


			




	151
	
	
		
        if( less(_data[child+1], _data[min]) )


			




	152
	
	
		
          min=child+1;


			




	153
	
	
		
      }


			




	154
	
	
		
      return min;


			




	155
	
	
		
    }


			




	156
	
	
		

			




	157
	134
	
		
    void bubbleUp(int hole, Pair p) {


			




	...
	...
	
		
@@ -169,10 +146,22 @@


			




	169
	146
	
		
        int child = firstChild(hole);


			




	170
	
	
		
        while( child<length ) {


			




	171
	
	
		
          child = findMin(child, length);


			




	172
	
	
		
          if( !less(_data[child], p) )


			




	
	147
	
		
        while( child+3<length ) {


			




	
	148
	
		
          int min=child;


			




	
	149
	
		
          if( less(_data[++child], _data[min]) ) min=child;


			




	
	150
	
		
          if( less(_data[++child], _data[min]) ) min=child;


			




	
	151
	
		
          if( less(_data[++child], _data[min]) ) min=child;


			




	
	152
	
		
          if( !less(_data[min], p) )


			




	173
	153
	
		
            goto ok;


			




	174
	
	
		
          move(_data[child], hole);


			




	175
	
	
		
          hole = child;


			




	
	154
	
		
          move(_data[min], hole);


			




	
	155
	
		
          hole = min;


			




	176
	156
	
		
          child = firstChild(hole);


			




	177
	157
	
		
        }


			




	
	158
	
		
        if ( child<length ) {


			




	
	159
	
		
          int min = child;


			




	
	160
	
		
          if( ++child<length && less(_data[child], _data[min]) ) min=child;


			




	
	161
	
		
          if( ++child<length && less(_data[child], _data[min]) ) min=child;


			




	
	162
	
		
          if( less(_data[min], p) ) {


			




	
	163
	
		
            move(_data[min], hole);


			




	
	164
	
		
            hole = min;


			




	
	165
	
		
          }


			




	
	166
	
		
        }


			




	178
	167
	
		
      }

			




        

    

    

    

        

            

                

                    lemon/kary_heap.h
                

                

                  
                  
                  
                  Show white space
                  6 line context
                

                
                  
                
            

        

        

            

            



	...
	...
	
		
@@ -140,12 +140,2 @@


			




	140
	140
	
		

			




	141
	
	
		
    int findMin(const int child, const int length) {


			




	142
	
	
		
      int min=child, i=1;


			




	143
	
	
		
      while( i<K && child+i<length ) {


			




	144
	
	
		
        if( less(_data[child+i], _data[min]) )


			




	145
	
	
		
          min=child+i;


			




	146
	
	
		
        ++i;


			




	147
	
	
		
      }


			




	148
	
	
		
      return min;


			




	149
	
	
		
    }


			




	150
	
	
		

			




	151
	141
	
		
    void bubbleUp(int hole, Pair p) {


			




	...
	...
	
		
@@ -163,10 +153,25 @@


			




	163
	153
	
		
        int child = firstChild(hole);


			




	164
	
	
		
        while( child<length ) {


			




	165
	
	
		
          child = findMin(child, length);


			




	166
	
	
		
          if( !less(_data[child], p) )


			




	
	154
	
		
        while( child+K<=length ) {


			




	
	155
	
		
          int min=child;


			




	
	156
	
		
          for (int i=1; i<K; ++i) {


			




	
	157
	
		
            if( less(_data[child+i], _data[min]) )


			




	
	158
	
		
              min=child+i;


			




	
	159
	
		
          }


			




	
	160
	
		
          if( !less(_data[min], p) )


			




	167
	161
	
		
            goto ok;


			




	168
	
	
		
          move(_data[child], hole);


			




	169
	
	
		
          hole = child;


			




	
	162
	
		
          move(_data[min], hole);


			




	
	163
	
		
          hole = min;


			




	170
	164
	
		
          child = firstChild(hole);


			




	171
	165
	
		
        }


			




	
	166
	
		
        if ( child<length ) {


			




	
	167
	
		
          int min = child;


			




	
	168
	
		
          while (++child < length) {


			




	
	169
	
		
            if( less(_data[child], _data[min]) )


			




	
	170
	
		
              min=child;


			




	
	171
	
		
          }


			




	
	172
	
		
          if( less(_data[min], p) ) {


			




	
	173
	
		
            move(_data[min], hole);


			




	
	174
	
		
            hole = min;


			




	
	175
	
		
          }


			




	
	176
	
		
        }


			




	172
	177
	
		
      }


			




        

    






    
    



    


    

     
    
0 comments (0 inline)