Changeset 753:9314d9339475 in lemon
 Timestamp:
 07/20/09 19:06:39 (11 years ago)
 Branch:
 default
 Phase:
 public
 Location:
 lemon
 Files:

 2 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 } 
lemon/kary_heap.h
r751 r753 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.