Fibonacci Heaps — Detailed Explanation
A Fibonacci Heap is an advanced priority queue data structure that supports extremely fast amortized time for operations—especially decrease-key and merge.
It is widely used in graph algorithms like Dijkstra and Prim, where decrease-key operations happen frequently.
1. What is a Fibonacci Heap?
A Fibonacci Heap is a collection of heap-ordered trees (usually min-heap).
It is similar to a Binomial heap but far more flexible.
Key idea:
👉 Fibonacci Heaps delay work until absolutely necessary, reducing amortized time.
2. Structure of a Fibonacci Heap
A Fibonacci Heap consists of:
- Root list → list of tree roots
- Child lists → children of each node
- Marked nodes → indicates if node has lost a child
- A pointer to minimum node
Nodes are stored in circular doubly linked lists, allowing O(1) insertion and merging.
3. Properties of Fibonacci Heap
- Each tree obeys min-heap property
- The structure is very relaxed—trees are not strictly binomial
- Trees will become binomial-like only during consolidation
- Node has:
- key value
- degree (#children)
- mark bit
- parent pointer
- child pointer
- left/right sibling pointers
4. Key Operations
Fibonacci Heaps are designed to excel in operations that traditional heaps do slowly.
A. Make-heap
Creates an empty heap.
Time → O(1)
B. Find-min
Return pointer to the minimum node.
Stored directly → O(1)
C. Insert(key)
- Create new singleton tree.
- Insert it into the root list.
- Update min pointer.
Time → O(1) amortized
This is faster than binary heap or binomial heap.
D. Merge (Union)
To merge H1 and H2:
- Concatenate their root lists.
- Update min pointer.
Time → O(1)
(Far better than Binomial Heap’s O(log n))
E. Extract-min (Delete-min)
Most important and most expensive operation.
Steps:
- Remove the min node.
- Add all its children to root list.
- Consolidate root list:
- Combine trees of same degree
- Use linking similar to binomial heaps
- Ensures at most O(log n) trees remain
Time → O(log n) amortized
F. Decrease-key (Most Important Operation)
This is where Fibonacci Heaps beat all other heaps.
Steps:
- Reduce the key value.
- If heap-order is violated:
- Cut the node and move it to root list
- Cascade cut:
- If parent is marked → cut parent too
- Continue up the tree
Time → O(1) amortized
(This is the main reason Dijkstra becomes faster.)
G. Delete
- Decrease-key to (-\infty)
- Extract-min
Time → O(log n)
5. Amortized Time Complexities
| Operation | Fibonacci Heap | Binomial Heap | Binary Heap |
|---|---|---|---|
| Make-heap | O(1) | O(1) | O(1) |
| Find-min | O(1) | O(log n) | O(1) |
| Insert | O(1) | O(log n) | O(log n) |
| Merge | O(1) | O(log n) | O(n) |
| Extract-min | O(log n) | O(log n) | O(log n) |
| Decrease-key | O(1) | O(log n) | O(log n) |
| Delete | O(log n) | O(log n) | O(log n) |
Highlight:
Decrease-key & merge = O(1) → extremely useful for graph algorithms.
6. Applications
Fibonacci Heaps are used for algorithms requiring frequent decrease-key:
A. Dijkstra’s Shortest Path Algorithm
- Using binary heap → O((V+E) log V)
- Using Fibonacci heap → O(E + V log V) (faster)
B. Prim’s Minimum Spanning Tree
- Better performance due to decrease-key = O(1)
C. Network routing tables
D. Event-driven simulation systems
E. Optimal merging of lists
Note: Real-world implementations often use pairing heaps due to simplicity, but Fibonacci heaps remain important theoretically.
7. Advantages of Fibonacci Heaps
✔ Very fast amortized time
✔ Best in theory for graph algorithms
✔ Fast merge operation
✔ Supports cascading cuts to maintain efficiency
✔ Flexible structure (lazy organization)
8. Disadvantages
✘ Complex to implement
✘ High constant factors → slower in practice
✘ Uses more memory
✘ Consolidation step can be tricky
✘ Rarely used in industry (pairing heap preferred)
9. Fibonacci Heap vs Binomial Heap
| Feature | Fibonacci Heap | Binomial Heap |
|---|---|---|
| Structure | Flexible | Strict binomial |
| Merge | O(1) | O(log n) |
| Decrease-key | O(1) | O(log n) |
| Extract-min | O(log n) | O(log n) |
| Implementation | Complex | Easier |
| Graph Algorithms | Best | Good |
Summary
A Fibonacci Heap is a powerful priority queue structure that uses:
- Lazy merging
- Cascading cuts
- Consolidation
- Multiple heap-ordered trees
Its amortized O(1) decrease-key and insert make it extremely valuable in theoretical optimization and graph algorithms.