Fibonacci Heaps: Amortized Bounds That Make Dijkstra Faster
What This Concept Is
A classical Fibonacci heap defers consolidation and uses marked nodes to control how much tree structure may degrade. Standard amortized bounds are O(1) for insert, meld and decrease-key, O(log n) for extract-min/delete, with O(1) minimum access via a maintained pointer. They require the specified handle-based operations, degree maintenance and cascading-cut rules.
Why It Matters Here
This is a proof-study topic, not a requirement to build a production Fibonacci heap. It illustrates how aggregate operation costs can improve an algorithmic bound without promising better measured performance or bounded single-call latency.
Concrete Examples
Use potential Phi = roots + 2*marked_nonroot_nodes under a compatible
primitive-operation cost scale. Insertion adds a root. Decrease-key that violates
parent order cuts the node; a nonroot that loses its first child becomes marked,
and loss of a second triggers a cut and may cascade. Cutting a marked node
removes two units of mark potential while adding a root, helping pay for work.
Constants must match the chosen primitive costs; potential is not money without units.
Extract-min promotes children to roots and consolidates equal degrees. The child-loss rule implies Fibonacci-like minimum subtree size as a function of degree, giving logarithmic maximum degree and controlling consolidation. That is a bound on degree, not on tree height. A classical heap can have a long chain, so cascading cuts need not be limited to O(log n) steps in one operation. The amortized bound pays across the sequence.
For Dijkstra with nonnegative weights and direct live handles, there are O(V) extract-min operations and O(E) potential successful decreases. This yields O(E+V log V) under the usual arithmetic/comparison model, plus initialization. If an implementation instead pushes duplicate entries, its operation counts and memory differ; changing the priority queue name alone does not prove the bound.
Common Confusion / Misconceptions
A delete operation needs the correct handle contract and cannot always simulate negative infinity with a finite sentinel in an arbitrary key domain. Pointer allocation, locality and workload can outweigh asymptotic improvements. Do not claim the Fibonacci heap is always faster than a binary heap.
How To Use It
Trace roots, marks, actual work and potential changes on insert, one cut, a cascade and extract-min. State what is proved by the degree lemma and what is not. Compare queue choices using operation counts and a measured workload only after matching handles, ties and update semantics.
Check Yourself
Why does marking track child loss rather than merely node depth? Why does logarithmic degree not imply logarithmic height? What queue API is needed for Dijkstra’s decrease-key count?
Mini Drill or Application
A heap has 5 roots and 3 marked nonroots. Insert one node. Feedback: potential goes from 11 to 12. Explain why this numeric change alone does not prove the entire extract-min bound.
Read This Only If Stuck
CLRS: Fibonacci heaps and their potential/degree arguments, where covered in your edition. Keep the source theorem and the illustrative potential trace distinct.