Changeset 706:9314d9339475 in lemon1.2 for lemon/kary_heap.h
 Timestamp:
 07/20/09 19:06:39 (12 years ago)
 Branch:
 default
 Phase:
 public
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/kary_heap.h
r704 r706 139 139 } 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) { 152 142 int par = parent(hole); … … 162 152 if( length>1 ) { 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); 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 } 171 176 } 172 177 }
Note: See TracChangeset
for help on using the changeset viewer.