Changeset 707:3887d6f994d7 in lemon1.2 for lemon/binom_heap.h
 Timestamp:
 07/24/09 01:07:45 (12 years ago)
 Branch:
 default
 Phase:
 public
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/binom_heap.h
r703 r707 80 80 81 81 private: 82 class store;83 84 std::vector< store> _data;82 class Store; 83 84 std::vector<Store> _data; 85 85 int _min, _head; 86 86 ItemIntMap &_iim; … … 157 157 int s=_data.size(); 158 158 _iim.set( item,s ); 159 store st;159 Store st; 160 160 st.name=item; 161 st.prio=value; 161 162 _data.push_back(st); 162 163 i=s; … … 166 167 _data[i].degree=0; 167 168 _data[i].in=true; 168 } 169 _data[i].prio=value; 170 171 if( 0==_num_items ) { _head=i; _min=i; } 172 else { merge(i); } 173 174 _min = findMin(); 175 169 _data[i].prio=value; 170 } 171 172 if( 0==_num_items ) { 173 _head=i; 174 _min=i; 175 } else { 176 merge(i); 177 if( _comp(_data[i].prio, _data[_min].prio) ) _min=i; 178 } 176 179 ++_num_items; 177 180 } … … 209 212 int child=_data[_min].child; 210 213 int neighb; 211 int prev=1;212 214 while( child!=1 ) { 213 215 neighb=_data[child].right_neighbor; 214 216 _data[child].parent=1; 215 _data[child].right_neighbor= prev;217 _data[child].right_neighbor=head_child; 216 218 head_child=child; 217 prev=child;218 219 child=neighb; 219 220 } 220 221 } 221 222 222 // The first case is that there are only one root.223 if ( 1==_data[_head].right_neighbor ) {223 if ( _data[_head].right_neighbor==1 ) { 224 // there was only one root 224 225 _head=head_child; 225 226 } 226 // The case where there are more roots.227 227 else { 228 // there were more roots 228 229 if( _head!=_min ) { unlace(_min); } 229 230 else { _head=_data[_head].right_neighbor; } 230 231 231 merge(head_child); 232 232 } … … 257 257 void decrease (Item item, const Prio& value) { 258 258 int i=_iim[item]; 259 260 if( _comp( value,_data[i].prio ) ) { 261 _data[i].prio=value; 262 263 int p_loc=_data[i].parent, loc=i; 264 int parent, child, neighb; 265 266 while( 1!=p_loc && _comp(_data[loc].prio,_data[p_loc].prio) ) { 267 268 // parent set for other loc_child 269 child=_data[loc].child; 270 while( 1!=child ) { 271 _data[child].parent=p_loc; 272 child=_data[child].right_neighbor; 273 } 274 275 // parent set for other p_loc_child 276 child=_data[p_loc].child; 277 while( 1!=child ) { 278 _data[child].parent=loc; 279 child=_data[child].right_neighbor; 280 } 281 282 child=_data[p_loc].child; 283 _data[p_loc].child=_data[loc].child; 284 if( child==loc ) 285 child=p_loc; 286 _data[loc].child=child; 287 288 // left_neighb set for p_loc 289 if( _data[loc].child!=p_loc ) { 290 while( _data[child].right_neighbor!=loc ) 291 child=_data[child].right_neighbor; 292 _data[child].right_neighbor=p_loc; 293 } 294 295 // left_neighb set for loc 296 parent=_data[p_loc].parent; 297 if( 1!=parent ) child=_data[parent].child; 298 else child=_head; 299 300 if( child!=p_loc ) { 301 while( _data[child].right_neighbor!=p_loc ) 302 child=_data[child].right_neighbor; 303 _data[child].right_neighbor=loc; 304 } 305 306 neighb=_data[p_loc].right_neighbor; 307 _data[p_loc].right_neighbor=_data[loc].right_neighbor; 308 _data[loc].right_neighbor=neighb; 309 310 _data[p_loc].parent=loc; 311 _data[loc].parent=parent; 312 313 if( 1!=parent && _data[parent].child==p_loc ) 314 _data[parent].child=loc; 315 316 /*if new parent will be the first root*/ 317 if( _head==p_loc ) 318 _head=loc; 319 320 p_loc=_data[loc].parent; 321 } 322 } 323 if( _comp(value,_data[_min].prio) ) { 324 _min=i; 325 } 259 int p=_data[i].parent; 260 _data[i].prio=value; 261 262 while( p!=1 && _comp(value, _data[p].prio) ) { 263 _data[i].name=_data[p].name; 264 _data[i].prio=_data[p].prio; 265 _data[p].name=item; 266 _data[p].prio=value; 267 _iim[_data[i].name]=i; 268 i=p; 269 p=_data[p].parent; 270 } 271 _iim[item]=i; 272 if ( _comp(value, _data[_min].prio) ) _min=i; 326 273 } 327 274 … … 376 323 377 324 private: 325 326 // Find the minimum of the roots 378 327 int findMin() { 379 int min_loc=1, min_val; 380 int x=_head; 381 if( x!=1 ) { 382 min_val=_data[x].prio; 383 min_loc=x; 384 x=_data[x].right_neighbor; 385 386 while( x!=1 ) { 328 if( _head!=1 ) { 329 int min_loc=_head, min_val=_data[_head].prio; 330 for( int x=_data[_head].right_neighbor; x!=1; 331 x=_data[x].right_neighbor ) { 387 332 if( _comp( _data[x].prio,min_val ) ) { 388 333 min_val=_data[x].prio; 389 334 min_loc=x; 390 335 } 391 x=_data[x].right_neighbor; 392 } 393 } 394 return min_loc; 395 } 396 336 } 337 return min_loc; 338 } 339 else return 1; 340 } 341 342 // Merge the heap with another heap starting at the given position 397 343 void merge(int a) { 398 interleave(a); 399 344 if( _head==1  a==1 ) return; 345 if( _data[a].right_neighbor==1 && 346 _data[a].degree<=_data[_head].degree ) { 347 _data[a].right_neighbor=_head; 348 _head=a; 349 } else { 350 interleave(a); 351 } 352 if( _data[_head].right_neighbor==1 ) return; 353 400 354 int x=_head; 401 if( 1!=x ) { 402 int x_prev=1, x_next=_data[x].right_neighbor; 403 while( 1!=x_next ) { 404 if( _data[x].degree!=_data[x_next].degree  ( 1!=_data[x_next].right_neighbor && _data[_data[x_next].right_neighbor].degree==_data[x].degree ) ) { 405 x_prev=x; 355 int x_prev=1, x_next=_data[x].right_neighbor; 356 while( x_next!=1 ) { 357 if( _data[x].degree!=_data[x_next].degree  358 ( _data[x_next].right_neighbor!=1 && 359 _data[_data[x_next].right_neighbor].degree==_data[x].degree ) ) { 360 x_prev=x; 361 x=x_next; 362 } 363 else { 364 if( _comp(_data[x_next].prio,_data[x].prio) ) { 365 if( x_prev==1 ) { 366 _head=x_next; 367 } else { 368 _data[x_prev].right_neighbor=x_next; 369 } 370 fuse(x,x_next); 406 371 x=x_next; 407 372 } 408 373 else { 409 if( _comp(_data[x].prio,_data[x_next].prio) ) { 410 _data[x].right_neighbor=_data[x_next].right_neighbor; 411 fuse(x_next,x); 412 } 413 else { 414 if( 1==x_prev ) { _head=x_next; } 415 else { 416 _data[x_prev].right_neighbor=x_next; 417 } 418 fuse(x,x_next); 419 x=x_next; 420 } 374 _data[x].right_neighbor=_data[x_next].right_neighbor; 375 fuse(x_next,x); 421 376 } 422 x_next=_data[x].right_neighbor; 423 } 424 } 425 } 426 377 } 378 x_next=_data[x].right_neighbor; 379 } 380 } 381 382 // Interleave the elements of the given list into the list of the roots 427 383 void interleave(int a) { 428 int other=1, head_other=1; 429 430 while( 1!=a  1!=_head ) { 431 if( 1==a ) { 432 if( 1==head_other ) { 433 head_other=_head; 434 } 435 else { 436 _data[other].right_neighbor=_head; 437 } 438 _head=1; 439 } 440 else if( 1==_head ) { 441 if( 1==head_other ) { 442 head_other=a; 443 } 444 else { 445 _data[other].right_neighbor=a; 446 } 447 a=1; 384 int p=_head, q=a; 385 int curr=_data.size(); 386 _data.push_back(Store()); 387 388 while( p!=1  q!=1 ) { 389 if( q==1  ( p!=1 && _data[p].degree<_data[q].degree ) ) { 390 _data[curr].right_neighbor=p; 391 curr=p; 392 p=_data[p].right_neighbor; 448 393 } 449 394 else { 450 if( _data[a].degree<_data[_head].degree ) { 451 if( 1==head_other ) { 452 head_other=a; 453 } 454 else { 455 _data[other].right_neighbor=a; 456 } 457 other=a; 458 a=_data[a].right_neighbor; 459 } 460 else { 461 if( 1==head_other ) { 462 head_other=_head; 463 } 464 else { 465 _data[other].right_neighbor=_head; 466 } 467 other=_head; 468 _head=_data[_head].right_neighbor; 469 } 470 } 471 } 472 _head=head_other; 473 } 474 475 // Lacing a under b 395 _data[curr].right_neighbor=q; 396 curr=q; 397 q=_data[q].right_neighbor; 398 } 399 } 400 401 _head=_data.back().right_neighbor; 402 _data.pop_back(); 403 } 404 405 // Lace node a under node b 476 406 void fuse(int a, int b) { 477 407 _data[a].parent=b; … … 482 412 } 483 413 484 // It is invoked only if a has siblings.414 // Unlace node a (if it has siblings) 485 415 void unlace(int a) { 486 416 int neighb=_data[a].right_neighbor; … … 494 424 private: 495 425 496 class store {426 class Store { 497 427 friend class BinomHeap; 498 428 … … 505 435 Prio prio; 506 436 507 store() : parent(1), right_neighbor(1), child(1), degree(0), in(true) {} 437 Store() : parent(1), right_neighbor(1), child(1), degree(0), 438 in(true) {} 508 439 }; 509 440 };
Note: See TracChangeset
for help on using the changeset viewer.