41 /// |
41 /// |
42 ///The methods \ref increase and \ref erase are not efficient in a Fibonacci |
42 ///The methods \ref increase and \ref erase are not efficient in a Fibonacci |
43 ///heap. In case of many calls to these operations, it is better to use a |
43 ///heap. In case of many calls to these operations, it is better to use a |
44 ///\e binary \e heap. |
44 ///\e binary \e heap. |
45 /// |
45 /// |
46 ///\param Item Type of the items to be stored. |
|
47 ///\param Prio Type of the priority of the items. |
46 ///\param Prio Type of the priority of the items. |
48 ///\param ItemIntMap A read and writable Item int map, used internally |
47 ///\param ItemIntMap A read and writable Item int map, used internally |
49 ///to handle the cross references. |
48 ///to handle the cross references. |
50 ///\param Compare A class for the ordering of the priorities. The |
49 ///\param Compare A class for the ordering of the priorities. The |
51 ///default is \c std::less<Prio>. |
50 ///default is \c std::less<Prio>. |
53 ///\sa BinHeap |
52 ///\sa BinHeap |
54 ///\sa Dijkstra |
53 ///\sa Dijkstra |
55 ///\author Jacint Szabo |
54 ///\author Jacint Szabo |
56 |
55 |
57 #ifdef DOXYGEN |
56 #ifdef DOXYGEN |
58 template <typename Item, |
57 template <typename Prio, |
59 typename Prio, |
|
60 typename ItemIntMap, |
58 typename ItemIntMap, |
61 typename Compare> |
59 typename Compare> |
62 #else |
60 #else |
63 template <typename Item, |
61 template <typename Prio, |
64 typename Prio, |
|
65 typename ItemIntMap, |
62 typename ItemIntMap, |
66 typename Compare = std::less<Prio> > |
63 typename Compare = std::less<Prio> > |
67 #endif |
64 #endif |
68 class FibHeap { |
65 class FibHeap { |
69 public: |
66 public: |
|
67 typedef typename ItemIntMap::Key Item; |
70 typedef Prio PrioType; |
68 typedef Prio PrioType; |
71 |
69 |
72 private: |
70 private: |
73 class store; |
71 class store; |
74 |
72 |
269 |
267 |
270 // ********************************************************************** |
268 // ********************************************************************** |
271 // IMPLEMENTATIONS |
269 // IMPLEMENTATIONS |
272 // ********************************************************************** |
270 // ********************************************************************** |
273 |
271 |
274 template <typename Item, typename Prio, typename ItemIntMap, |
272 template <typename Prio, typename ItemIntMap, |
275 typename Compare> |
273 typename Compare> |
276 void FibHeap<Item, Prio, ItemIntMap, Compare>::set |
274 void FibHeap<Prio, ItemIntMap, Compare>::set |
277 (Item const item, PrioType const value) |
275 (Item const item, PrioType const value) |
278 { |
276 { |
279 int i=iimap[item]; |
277 int i=iimap[item]; |
280 if ( i >= 0 && container[i].in ) { |
278 if ( i >= 0 && container[i].in ) { |
281 if ( comp(value, container[i].prio) ) decrease(item, value); |
279 if ( comp(value, container[i].prio) ) decrease(item, value); |
282 if ( comp(container[i].prio, value) ) increase(item, value); |
280 if ( comp(container[i].prio, value) ) increase(item, value); |
283 } else push(item, value); |
281 } else push(item, value); |
284 } |
282 } |
285 |
283 |
286 template <typename Item, typename Prio, typename ItemIntMap, |
284 template <typename Prio, typename ItemIntMap, |
287 typename Compare> |
285 typename Compare> |
288 void FibHeap<Item, Prio, ItemIntMap, Compare>::push |
286 void FibHeap<Prio, ItemIntMap, Compare>::push |
289 (Item const item, PrioType const value) { |
287 (Item const item, PrioType const value) { |
290 int i=iimap[item]; |
288 int i=iimap[item]; |
291 if ( i < 0 ) { |
289 if ( i < 0 ) { |
292 int s=container.size(); |
290 int s=container.size(); |
293 iimap.set( item, s ); |
291 iimap.set( item, s ); |
314 } |
312 } |
315 container[i].prio=value; |
313 container[i].prio=value; |
316 ++num_items; |
314 ++num_items; |
317 } |
315 } |
318 |
316 |
319 template <typename Item, typename Prio, typename ItemIntMap, |
317 template <typename Prio, typename ItemIntMap, |
320 typename Compare> |
318 typename Compare> |
321 void FibHeap<Item, Prio, ItemIntMap, Compare>::pop() { |
319 void FibHeap<Prio, ItemIntMap, Compare>::pop() { |
322 /*The first case is that there are only one root.*/ |
320 /*The first case is that there are only one root.*/ |
323 if ( container[minimum].left_neighbor==minimum ) { |
321 if ( container[minimum].left_neighbor==minimum ) { |
324 container[minimum].in=false; |
322 container[minimum].in=false; |
325 if ( container[minimum].degree!=0 ) { |
323 if ( container[minimum].degree!=0 ) { |
326 makeroot(container[minimum].child); |
324 makeroot(container[minimum].child); |
348 } // the case where there are more roots |
346 } // the case where there are more roots |
349 --num_items; |
347 --num_items; |
350 } |
348 } |
351 |
349 |
352 |
350 |
353 template <typename Item, typename Prio, typename ItemIntMap, |
351 template <typename Prio, typename ItemIntMap, |
354 typename Compare> |
352 typename Compare> |
355 void FibHeap<Item, Prio, ItemIntMap, Compare>::erase |
353 void FibHeap<Prio, ItemIntMap, Compare>::erase |
356 (const Item& item) { |
354 (const Item& item) { |
357 int i=iimap[item]; |
355 int i=iimap[item]; |
358 |
356 |
359 if ( i >= 0 && container[i].in ) { |
357 if ( i >= 0 && container[i].in ) { |
360 if ( container[i].parent!=-1 ) { |
358 if ( container[i].parent!=-1 ) { |
365 minimum=i; //As if its prio would be -infinity |
363 minimum=i; //As if its prio would be -infinity |
366 pop(); |
364 pop(); |
367 } |
365 } |
368 } |
366 } |
369 |
367 |
370 template <typename Item, typename Prio, typename ItemIntMap, |
368 template <typename Prio, typename ItemIntMap, |
371 typename Compare> |
369 typename Compare> |
372 void FibHeap<Item, Prio, ItemIntMap, Compare>::decrease |
370 void FibHeap<Prio, ItemIntMap, Compare>::decrease |
373 (Item item, PrioType const value) { |
371 (Item item, PrioType const value) { |
374 int i=iimap[item]; |
372 int i=iimap[item]; |
375 container[i].prio=value; |
373 container[i].prio=value; |
376 int p=container[i].parent; |
374 int p=container[i].parent; |
377 |
375 |
381 } |
379 } |
382 if ( comp(value, container[minimum].prio) ) minimum=i; |
380 if ( comp(value, container[minimum].prio) ) minimum=i; |
383 } |
381 } |
384 |
382 |
385 |
383 |
386 template <typename Item, typename Prio, typename ItemIntMap, |
384 template <typename Prio, typename ItemIntMap, |
387 typename Compare> |
385 typename Compare> |
388 void FibHeap<Item, Prio, ItemIntMap, Compare>::balance() { |
386 void FibHeap<Prio, ItemIntMap, Compare>::balance() { |
389 |
387 |
390 int maxdeg=int( std::floor( 2.08*log(double(container.size()))))+1; |
388 int maxdeg=int( std::floor( 2.08*log(double(container.size()))))+1; |
391 |
389 |
392 std::vector<int> A(maxdeg,-1); |
390 std::vector<int> A(maxdeg,-1); |
393 |
391 |
426 if ( comp(container[s].prio, container[minimum].prio) ) minimum=s; |
424 if ( comp(container[s].prio, container[minimum].prio) ) minimum=s; |
427 s=container[s].right_neighbor; |
425 s=container[s].right_neighbor; |
428 } while ( s != m ); |
426 } while ( s != m ); |
429 } |
427 } |
430 |
428 |
431 template <typename Item, typename Prio, typename ItemIntMap, |
429 template <typename Prio, typename ItemIntMap, |
432 typename Compare> |
430 typename Compare> |
433 void FibHeap<Item, Prio, ItemIntMap, Compare>::makeroot |
431 void FibHeap<Prio, ItemIntMap, Compare>::makeroot |
434 (int c) { |
432 (int c) { |
435 int s=c; |
433 int s=c; |
436 do { |
434 do { |
437 container[s].parent=-1; |
435 container[s].parent=-1; |
438 s=container[s].right_neighbor; |
436 s=container[s].right_neighbor; |
439 } while ( s != c ); |
437 } while ( s != c ); |
440 } |
438 } |
441 |
439 |
442 |
440 |
443 template <typename Item, typename Prio, typename ItemIntMap, |
441 template <typename Prio, typename ItemIntMap, |
444 typename Compare> |
442 typename Compare> |
445 void FibHeap<Item, Prio, ItemIntMap, Compare>::cut |
443 void FibHeap<Prio, ItemIntMap, Compare>::cut |
446 (int a, int b) { |
444 (int a, int b) { |
447 /* |
445 /* |
448 *Replacing a from the children of b. |
446 *Replacing a from the children of b. |
449 */ |
447 */ |
450 --container[b].degree; |
448 --container[b].degree; |
467 container[a].parent=-1; |
465 container[a].parent=-1; |
468 container[a].marked=false; |
466 container[a].marked=false; |
469 } |
467 } |
470 |
468 |
471 |
469 |
472 template <typename Item, typename Prio, typename ItemIntMap, |
470 template <typename Prio, typename ItemIntMap, |
473 typename Compare> |
471 typename Compare> |
474 void FibHeap<Item, Prio, ItemIntMap, Compare>::cascade |
472 void FibHeap<Prio, ItemIntMap, Compare>::cascade |
475 (int a) |
473 (int a) |
476 { |
474 { |
477 if ( container[a].parent!=-1 ) { |
475 if ( container[a].parent!=-1 ) { |
478 int p=container[a].parent; |
476 int p=container[a].parent; |
479 |
477 |
484 } |
482 } |
485 } |
483 } |
486 } |
484 } |
487 |
485 |
488 |
486 |
489 template <typename Item, typename Prio, typename ItemIntMap, |
487 template <typename Prio, typename ItemIntMap, |
490 typename Compare> |
488 typename Compare> |
491 void FibHeap<Item, Prio, ItemIntMap, Compare>::fuse |
489 void FibHeap<Prio, ItemIntMap, Compare>::fuse |
492 (int a, int b) { |
490 (int a, int b) { |
493 unlace(b); |
491 unlace(b); |
494 |
492 |
495 /*Lacing b under a.*/ |
493 /*Lacing b under a.*/ |
496 container[b].parent=a; |
494 container[b].parent=a; |
515 |
513 |
516 |
514 |
517 /* |
515 /* |
518 *It is invoked only if a has siblings. |
516 *It is invoked only if a has siblings. |
519 */ |
517 */ |
520 template <typename Item, typename Prio, typename ItemIntMap, |
518 template <typename Prio, typename ItemIntMap, |
521 typename Compare> |
519 typename Compare> |
522 void FibHeap<Item, Prio, ItemIntMap, Compare>::unlace |
520 void FibHeap<Prio, ItemIntMap, Compare>::unlace |
523 (int a) { |
521 (int a) { |
524 int leftn=container[a].left_neighbor; |
522 int leftn=container[a].left_neighbor; |
525 int rightn=container[a].right_neighbor; |
523 int rightn=container[a].right_neighbor; |
526 container[leftn].right_neighbor=rightn; |
524 container[leftn].right_neighbor=rightn; |
527 container[rightn].left_neighbor=leftn; |
525 container[rightn].left_neighbor=leftn; |