Changeset 706:9314d9339475 in lemon-1.2 for lemon/kary_heap.h
- Timestamp:
- 07/20/09 19:06:39 (15 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.