Question
Implement a Fibonacci Heap supporting insert, meld, find-min, extract-min, decrease-key, and delete. Explain how root lists, parent-child links, degree, mark bits, and cascading cuts work together, and use a potential function to show why insert, meld, find-min, and decrease-key are O(1) amortized while extract-min is O(log n) amortized.
What the interviewer is testing
- Whether you distinguish actual cost from amortized cost instead of saying every O(1) amortized operation is always O(1).
- Whether you maintain circular doubly linked lists, the minimum-root pointer, node handles, and parent pointers.
- Whether decrease-key correctly performs cuts, marking, and cascading cuts.
- Whether you can explain the theoretical advantage, engineering constants, and trade-offs against pairing and binary heaps.
Model answer
A Fibonacci Heap is a collection of heap-ordered trees. Roots form a circular doubly linked list, and each node stores a parent, child list, degree, and mark bit. The structure delays consolidation until extract-min, when roots are linked by degree.
insert adds a node to the root list and updates the minimum; meld splices two root lists. If decrease-key violates heap order, cut the node from its parent and add it to the root list. If the parent has already lost a child, recursively perform a cascading cut. A mark records whether a node has already lost one child and limits cascading damage.
extract-min promotes the minimum root’s children to the root list, removes that root, and repeatedly links roots with equal degree. A common potential is the number of roots plus twice the number of marked nodes. Insert and meld increase roots but pay only a constant; cascading cuts reduce marked nodes and are paid by potential. The number of links in extract-min is bounded by O(log n) because heap order limits the maximum degree.
Implementation sketch
The pseudocode shows the critical decrease-key path; the caller owns the node handle.
decreaseKey(x, newKey):
if newKey > x.key: error
x.key = newKey
p = x.parent
if p is not empty and x.key < p.key:
cut(x, p)
cascadingCut(p)
if x.key < min.key:
min = x
cut(x, p):
removeFromChildList(p, x)
p.degree -= 1
addToRootList(x)
x.parent = empty
x.mark = false
cascadingCut(y):
p = y.parent
if p is empty: return
if y.mark is false:
y.mark = true
else:
cut(y, p)
cascadingCut(p)During extract-min, safely save the next pointer while promoting children before removing the minimum root. Linking equal-degree roots must update parent, child, degree, and mark, followed by a scan for the new minimum.
Common pitfalls
- Writing an array-based binary heap and claiming it has Fibonacci Heap O(1) amortized decrease-key.
- Forgetting to clear parent or mark after a cut, corrupting the next cascade.
- Deleting from a circular doubly linked list while using an invalid next pointer.
- Comparing only old roots after extract-min and forgetting promoted children in the root list and minimum scan.
- Comparing only asymptotic bounds while ignoring pointer chasing, cache locality, allocation, and implementation complexity.
Complexity trade-offs
When decrease-key is frequent, meld is needed, and amortized analysis is acceptable, Fibonacci Heap has an attractive theoretical bound; the classic examples are improved bounds for Prim’s and Dijkstra’s algorithms. In production, pairing heaps, rank-pairing heaps, or binary heaps often compete better because they are simpler and more cache-friendly.
The bounds assume node handles. If callers can only find nodes by key, an auxiliary index changes the design. A concurrent implementation must also define ownership of root lists and handles; lock-free safety does not follow from amortized analysis.
Test a singleton, duplicate keys, meld with an empty heap, repeated decrease-key, and deleting the last node. Generate random operation sequences and compare minimum values and extract-min order with a reference priority queue. Construct a node that loses two children in sequence to verify that the first loss marks it and the second loss cuts it.
References
- MIT OpenCourseWare Fibonacci heaps lecture: potential analysis and decrease-key/extract-min bounds.
- Fibonacci Heaps Revisited: a reanalysis of cascading cuts and amortized bounds.
- Fredman and Tarjan’s original paper: Fibonacci heaps and their use in network optimization algorithms.
Follow-up questions
Why do marked nodes contribute two units to the potential?
A cascading cut removes one marked node and adds one root. Two units of potential pay for clearing the mark and adding the root, keeping the amortized cost of the entire cascade constant.
Why is extract-min O(log n) amortized?
After removing the minimum and promoting its children, consolidation keeps at most one root per degree. Heap order ties a node’s degree to its subtree size, so the maximum degree is O(log n), bounding the number of links.
Why can meld be O(1) amortized?
Two circular root lists can be spliced directly and their minimum pointers compared. Equal-degree trees are not consolidated until a later extract-min.
When is a binary heap a better choice?
Use a binary heap when decrease-key is rare, array locality matters, node handles are inconvenient, or the team values a simpler implementation. It provides O(log n) operations with predictable memory behavior.
How do you implement delete?
Lower the node’s key to negative infinity and call extract-min. A production implementation must define the key domain, sentinel behavior, and handle invalidation so a valid business key is never mistaken for the sentinel.