Changeset 705:39a5b48bcace in lemon1.2
 Timestamp:
 07/10/09 09:17:13 (12 years ago)
 Branch:
 default
 Phase:
 public
 Location:
 lemon
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

lemon/fourary_heap.h
r703 r705 166 166 167 167 void bubbleDown(int hole, Pair p, int length) { 168 int child = firstChild(hole); 169 while( child<length && length>1 ) { 170 child = findMin(child,length); 171 if( !less(_data[child], p) ) 172 goto ok; 173 move(_data[child], hole); 174 hole = child; 175 child = firstChild(hole); 168 if( length>1 ) { 169 int child = firstChild(hole); 170 while( child<length ) { 171 child = findMin(child, length); 172 if( !less(_data[child], p) ) 173 goto ok; 174 move(_data[child], hole); 175 hole = child; 176 child = firstChild(hole); 177 } 176 178 } 177 179 ok: 
lemon/pairing_heap.h
r703 r705 209 209 /// \pre The heap must be nonempty. 210 210 void pop() { 211 int TreeArray[_num_items];212 int i=0, num_child=0,child_right = 0;211 std::vector<int> trees; 212 int i=0, child_right = 0; 213 213 _data[_min].in=false; 214 214 215 215 if( 1!=_data[_min].child ) { 216 216 i=_data[_min].child; 217 TreeArray[num_child] = i;217 trees.push_back(i); 218 218 _data[i].parent = 1; 219 219 _data[_min].child = 1; 220 220 221 ++num_child;222 221 int ch=1; 223 222 while( _data[i].child!=1 ) { 224 223 ch=_data[i].child; 225 224 if( _data[ch].left_child && i==_data[ch].parent ) { 226 i=ch; 227 //break; 225 break; 228 226 } else { 229 227 if( _data[ch].left_child ) { … … 238 236 } 239 237 _data[child_right].parent = 1; 240 TreeArray[num_child] = child_right;238 trees.push_back(child_right); 241 239 i = child_right; 242 ++num_child;243 244 } 245 240 } 241 } 242 243 int num_child = trees.size(); 246 244 int other; 247 245 for( i=0; i<num_child1; i+=2 ) { 248 if ( !_comp(_data[TreeArray[i]].prio, 249 _data[TreeArray[i+1]].prio) ) { 250 other=TreeArray[i]; 251 TreeArray[i]=TreeArray[i+1]; 252 TreeArray[i+1]=other; 253 } 254 fuse( TreeArray[i], TreeArray[i+1] ); 246 if ( !_comp(_data[trees[i]].prio, _data[trees[i+1]].prio) ) { 247 other=trees[i]; 248 trees[i]=trees[i+1]; 249 trees[i+1]=other; 250 } 251 fuse( trees[i], trees[i+1] ); 255 252 } 256 253 257 254 i = (0==(num_child % 2)) ? num_child2 : num_child1; 258 255 while(i>=2) { 259 if ( _comp(_data[TreeArray[i]].prio, 260 _data[TreeArray[i2]].prio) ) { 261 other=TreeArray[i]; 262 TreeArray[i]=TreeArray[i2]; 263 TreeArray[i2]=other; 264 } 265 fuse( TreeArray[i2], TreeArray[i] ); 256 if ( _comp(_data[trees[i]].prio, _data[trees[i2]].prio) ) { 257 other=trees[i]; 258 trees[i]=trees[i2]; 259 trees[i2]=other; 260 } 261 fuse( trees[i2], trees[i] ); 266 262 i=2; 267 263 } 268 _min = TreeArray[0]; 269 } 270 271 if ( 0==num_child ) { 264 _min = trees[0]; 265 } 266 else { 272 267 _min = _data[_min].child; 273 268 } 274 269 275 270 if (_min >= 0) _data[_min].left_child = false; 276 277 271 _num_items; 278 272 }
Note: See TracChangeset
for help on using the changeset viewer.