Fibonacci Heap: Could i always consolidate?

Question

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

Answer 1

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)$.