Right now I am learning about Fibonacci heaps for the first time. After the minimum Node of a Fibonacci heap is extracted you consolidate it, to give it a better structure and execute future operations faster. But why don't you consolidate the Heap more often, like after the insertion of 10 nodes with no consolidation in the meantime? Is it even possible to Consolidate whenever the heap feels like it? The consolidation would never break the structure, even if it is not executed after the ExtractMin()-Operation, am I right? Assuming that, I am right why is the consolidation not executed more often? Because it just makes no sense, as it doesn't make it faster or could it make it even slower?

Best regards, Alex

  • 2
    $\begingroup$ Wouldn't it just make everything take more time? like, running the consolidation algorithm takes time by itself, and there is probably no real benefit to use it even more than what it currently is used $\endgroup$
    – nir shahar
    Jun 5 at 11:29
  • $\begingroup$ ok, but it would be possible to do it whenever you want, it's just useless? $\endgroup$
    – lxg95
    Jun 5 at 13:19
  • $\begingroup$ If you do it more than necessary then its possible you will hurt the amortized running time. So use it only when necessary $\endgroup$
    – nir shahar
    Jun 5 at 13:21

In a Fibonacci heap, delete-min takes $O(\log n)$ amortised time, and insert, find-min, and decrease-key all take $O(1)$ amortised time. You could consolidate when you insert or decrease-key, but then they would take $O(\log n)$ amortised time.

To see why this is an advantage, consider what you would typically use a priority queue with decrease-key for, such as shortest path through a graph, or A* search. For each step, you delete-min an item, then you process it, then you insert or decrease-key its successor items.

With a Fibonacci heap, you pay $O(\log n)$ amortised cost per entry that you process. The operations that you perform on the successor entries have constant-time cost.

Dijkstra's shortest paths algorithm in a case in point. If insert and decrease-key had $O(\log n)$ cost, then its complexity would be $\Theta((V + E) \log V)$. Using a Fibonacci heap, its complexity is $\Theta(E + V \log V)$.


Your Answer

