Fibonacci Heap
Introduction
A Fibonacci Heap is an improvement over the Binomial Heap. Unlike a Binomial Heap, it does not immediately combine trees having the same degree. Instead, it postpones consolidation until the Extract-Min operation.
This lazy approach makes insertion and merging extremely fast, resulting in better amortized running time for many operations.
Why Do We Need Fibonacci Heap?
Suppose a navigation system continuously updates the shortest route while traffic conditions keep changing. The priority queue must repeatedly update node priorities. A Binary Heap or Binomial Heap performs these updates relatively slower, whereas a Fibonacci Heap performs the Decrease-Key operation in O(1) amortized time.
| Binary Heap | Binomial Heap | Fibonacci Heap |
|---|---|---|
| Simple structure | Collection of Binomial Trees | Collection of Heap Ordered Trees |
| Merge is costly | Merge is efficient | Merge is extremely efficient |
| Decrease-Key : O(log n) | O(log n) | O(1) Amortized |
| Suitable for simple priority queues | Suitable for multiple heaps | Best for graph algorithms |
Real-Life Example
Consider a GPS navigation system such as Google Maps. Whenever road conditions change, the shortest path must be recalculated. Since the priorities of vertices change frequently, the Decrease-Key operation is executed many times. A Fibonacci Heap performs this operation very efficiently, making it ideal for shortest-path algorithms.
Characteristics of Fibonacci Heap
- Collection of heap ordered trees.
- Supports lazy consolidation.
- Root nodes are connected using a circular doubly linked list.
- Maintains a pointer to the minimum element.
- Supports Merge in O(1) amortized time.
- Supports Decrease-Key in O(1) amortized time.
- Extract-Min performs consolidation.
Fibonacci Heap Structure
Figure 1 : Structure of a Fibonacci Heap consisting of multiple heap ordered trees connected through a circular doubly linked list.
Key Components of Fibonacci Heap
| Component | Description |
|---|---|
| Root List | Stores all root nodes in a circular doubly linked list. |
| Minimum Pointer | Points to the smallest root node. |
| Child Pointer | Points to the leftmost child of a node. |
| Degree | Represents the number of children of a node. |
| Mark Bit | Indicates whether a child has been cut previously. |
- Unlike Binomial Heap, trees are not immediately merged.
- Consolidation occurs only after Extract-Min.
- This lazy strategy provides excellent amortized complexity.
Internal Structure of a Fibonacci Heap
A Fibonacci Heap is composed of multiple heap-ordered trees. Unlike a Binomial Heap, these trees are not immediately merged after insertion. Instead, they remain separate until the Extract-Min operation, where trees of the same degree are consolidated.
All root nodes are connected through a circular doubly linked list, allowing efficient insertion and merging operations.
Node Structure
Each node of a Fibonacci Heap contains several fields that help maintain the heap structure efficiently.
| Field | Description |
|---|---|
| Key | Stores the value of the node. |
| Degree | Number of child nodes. |
| Parent Pointer | Points to the parent node. |
| Child Pointer | Points to one of its children. |
| Left Pointer | Points to the previous sibling. |
| Right Pointer | Points to the next sibling. |
| Mark Bit | Indicates whether a child has already been cut. |
Structure of a Fibonacci Heap
Figure 2 : Internal Structure showing the Root List, Child Pointers and Heap Ordered Trees.
Properties of Fibonacci Heap
- Collection of heap ordered trees.
- Every tree satisfies the Min Heap Property.
- Root nodes are connected through a circular doubly linked list.
- A pointer to the minimum node is always maintained.
- Each node stores degree and mark information.
- Trees are consolidated only during Extract-Min.
- Supports lazy evaluation.
Basic Operations Supported
| Operation | Description |
|---|---|
| Create Heap | Create an empty Fibonacci Heap. |
| Insert | Insert a new node into the root list. |
| Find Minimum | Return the node pointed to by the minimum pointer. |
| Merge | Join the root lists of two Fibonacci Heaps. |
| Extract Minimum | Remove the minimum node and consolidate trees. |
| Decrease Key | Reduce the key value of a node. |
| Delete | Delete any node from the heap. |
How a Fibonacci Heap Works
Step 2 : Insert new nodes into the root list.
Step 3 : Maintain the minimum pointer.
Step 4 : Perform Merge whenever two heaps are combined.
Step 5 : During Extract-Min, remove the minimum node and perform consolidation of trees having the same degree.
- Insertion never combines trees immediately.
- Merge simply concatenates the root lists.
- Consolidation is delayed until Extract-Min.
- This lazy approach gives excellent amortized performance.
Basic Operations on Fibonacci Heap
A Fibonacci Heap supports several efficient operations that make it one of the fastest priority queue data structures for graph algorithms. Most operations have excellent amortized time complexity because the heap delays structural changes until they are actually required.
| Operation | Description |
|---|---|
| Create Heap | Create an empty Fibonacci Heap. |
| Insert | Insert a new node into the root list. |
| Find Minimum | Return the minimum node. |
| Merge (Union) | Join two Fibonacci Heaps. |
| Extract Minimum | Remove the minimum node and consolidate trees. |
| Decrease Key | Reduce the key value of a node. |
| Delete | Delete any node from the heap. |
1. Create Heap Operation
Initially, the Fibonacci Heap is empty.
Initially there are no nodes and the minimum pointer is NULL.
2. Insert Operation
Insertion is one of the fastest operations in a Fibonacci Heap. A new node is simply added to the circular doubly linked root list. No tree merging is performed during insertion.
- Create a new node.
- Insert it into the root list.
- Update the minimum pointer if necessary.
Figure 3 : Inserting a New Node into the Root List.
Suppose the heap contains 7, 17, 24, 26
Insert 5
Since 5 is smaller than the current minimum, the minimum pointer is updated to 5. No consolidation is performed.
3. Find Minimum Operation
A Fibonacci Heap always maintains a pointer to the smallest root node. Therefore, finding the minimum element requires only constant time.
4. Merge (Union) Operation
The Merge operation joins the root lists of two Fibonacci Heaps. Since both heaps already use circular doubly linked lists, merging is performed by simply concatenating the two root lists.
No consolidation is performed immediately.
Figure 4 : Merge (Union) of Two Fibonacci Heaps.
Worked Example
| Step | Operation | Result |
|---|---|---|
| 1 | Create Empty Heap | Root List is Empty |
| 2 | Insert 12 | Minimum = 12 |
| 3 | Insert 8 | Minimum = 8 |
| 4 | Insert 25 | Added to Root List |
| 5 | Insert 18 | Added to Root List |
| 6 | Merge Another Heap | Root Lists Combined |
5. Extract Minimum Operation
The Extract-Min operation removes the node pointed to by the minimum pointer. This is the most expensive operation because it performs tree consolidation after deleting the minimum node.
The children of the deleted node are first added to the root list. After that, all trees having the same degree are merged together.
Figure 5 : Extract-Min Operation in Fibonacci Heap.
6. Consolidation
After removing the minimum node, multiple trees having the same degree may exist. The Consolidation process repeatedly merges such trees until no two trees have the same degree.
| Step | Operation |
|---|---|
| 1 | Find two trees having the same degree. |
| 2 | Compare their root keys. |
| 3 | Attach the larger root below the smaller root. |
| 4 | Increase the degree of the parent node. |
| 5 | Repeat until every degree becomes unique. |
Figure 6 : Consolidation of Trees having Equal Degree.
7. Decrease-Key Operation
Decrease-Key reduces the value of a node. If the heap property is violated, the node is cut from its parent and moved directly to the root list.
Suppose node 28 is changed to 6.
Since 6 becomes smaller than its parent, the node is removed from its current tree and inserted into the root list.
8. Cascading Cut
Whenever a child node is cut, its parent is marked. If the marked parent loses another child, it is also cut and moved to the root list. This recursive process is known as Cascading Cut.
9. Delete Operation
Deletion of a node is performed using two operations.
- Decrease the key to negative infinity.
- Perform Extract-Min.
Worked Example
Insert the following keys into an empty Fibonacci Heap.
7, 24, 17, 26, 18, 30, 21
| Step | Operation | Result |
|---|---|---|
| 1 | Insert 7 | Minimum = 7 |
| 2 | Insert 24 | Added to Root List |
| 3 | Insert 17 | Added to Root List |
| 4 | Insert 26 | Added to Root List |
| 5 | Extract-Min | Consolidation Begins |
| 6 | Merge Equal Degree Trees | Balanced Heap |
Time Complexity Analysis
The following table summarizes the amortized time complexity of various Fibonacci Heap operations.
| Operation | Amortized Time Complexity | Worst Case |
|---|---|---|
| Create Heap | O(1) | O(1) |
| Insert | O(1) | O(1) |
| Find Minimum | O(1) | O(1) |
| Merge (Union) | O(1) | O(1) |
| Extract Minimum | O(log n) | O(log n) |
| Decrease Key | O(1) | O(log n) |
| Delete | O(log n) | O(log n) |
| Space Complexity | O(n) | O(n) |
Comparison : Binomial Heap vs Fibonacci Heap
Figure 7 : Comparison between Binomial Heap and Fibonacci Heap.
| Feature | Binomial Heap | Fibonacci Heap |
|---|---|---|
| Structure | Binomial Trees | Heap Ordered Trees |
| Merge | O(log n) | O(1) |
| Insert | O(log n) | O(1) |
| Decrease-Key | O(log n) | O(1) |
| Extract-Min | O(log n) | O(log n) |
| Implementation | Moderate | Complex |
Advantages of Fibonacci Heap
- Very fast insertion operation.
- Merge operation requires constant time.
- Decrease-Key operation is extremely efficient.
- Suitable for large graph algorithms.
- Excellent amortized performance.
- Ideal for dynamic priority queues.
- Supports lazy consolidation.
Disadvantages of Fibonacci Heap
- Complex implementation.
- Requires additional memory for pointers.
- Difficult to debug.
- Larger constant factors than Binary Heap.
- Less suitable for small applications.
Applications of Fibonacci Heap
- Dijkstra's Shortest Path Algorithm.
- Prim's Minimum Spanning Tree Algorithm.
- Network Routing.
- Operating System Scheduling.
- Artificial Intelligence Search Algorithms.
- Cloud Computing Task Scheduling.
- Priority Queue Implementation.
- Graph Processing Systems.
Frequently Asked Interview Questions
- What is a Fibonacci Heap?
- Why is Fibonacci Heap faster than Binomial Heap?
- Explain the Merge operation.
- What is lazy consolidation?
- Explain Cascading Cut.
- Why is Decrease-Key O(1) amortized?
- How does Extract-Min work?
- Differentiate Binary Heap, Binomial Heap and Fibonacci Heap.
- Where is Fibonacci Heap used?
- Explain the Mark Bit.
Practice Questions
- Construct a Fibonacci Heap by inserting 12, 7, 20, 18, 3, 25 and 30.
- Perform the Merge operation on two Fibonacci Heaps.
- Illustrate the Extract-Min operation.
- Explain the Consolidation process with a suitable example.
- Explain Cascading Cut with a neat diagram.
- Compare Binomial Heap and Fibonacci Heap.
- Explain all Fibonacci Heap operations with time complexity.
- Write the algorithm for Decrease-Key.
Key Takeaways
- Fibonacci Heap is an advanced priority queue.
- Insertion and Merge take O(1) amortized time.
- Decrease-Key is the biggest advantage.
- Consolidation occurs only during Extract-Min.
- Cascading Cut improves amortized performance.
- Used extensively in graph algorithms.
Summary
A Fibonacci Heap is one of the most efficient priority queue data structures for graph algorithms. It supports constant amortized time for Insertion, Merge and Decrease-Key operations while maintaining logarithmic time for Extract-Min. The lazy consolidation strategy and cascading cut mechanism make it significantly more efficient than Binomial Heap in applications involving frequent priority updates.