Changeset 753:9314d9339475 in lemon for lemon/fourary_heap.h
- Timestamp:
- 07/20/09 19:06:39 (15 years ago)
- Branch:
- default
- Phase:
- public
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/fourary_heap.h
r752 r753 132 132 } 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) { 158 135 int par = parent(hole); … … 168 145 if( length>1 ) { 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); 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 } 177 166 } 178 167 }
Note: See TracChangeset
for help on using the changeset viewer.