The Fibonacci Heap is a data structure that provides efficient operations for priority queues. It was introduced by Michael L. Fredman and Robert E. Tarjan in 1984 and is named after the mathematician Leonardo Fibonacci. This heap has a unique property that allows for constant time amortized complexity for several important operations.
Structure of a Fibonacci Heap
A Fibonacci Heap is a collection of min-heap-ordered trees. Each tree follows the min-heap property, which means the key value of each node is greater than or equal to the key value of its parent. The root list of the heap is a circular, doubly linked list that contains pointers to each tree in the heap.
Merging Two Fibonacci Heaps
One of the key advantages of using Fibonacci Heaps is their ability to merge efficiently. When merging two heaps, the roots of both heaps are combined into a single circular, doubly linked list. The minimum pointer is updated if necessary.
Here’s an example to illustrate this process:
Heap 1: Heap 2: Merged Heap:
5 9 5
/ | \ / / | \
8 10 12 + 11 = 8 9 10
| | |
14 12 11
In this example, we merge Heap 1 (with roots {5,8}) and Heap 2 (with root {9,11}). The resulting merged heap has roots {5,8,9,10,11}.
Fibonacci Heap Operations
Fibonacci Heaps support several operations with efficient time complexities:
- Insertion: To insert a new element into the heap, a new tree is created with a single node. This tree is then merged with the root list. The overall time complexity is O(1).
- Merge: As mentioned earlier, merging two Fibonacci Heaps takes constant time O(1).
- Find Minimum: The minimum element in the heap can be found in O(1) time by accessing the minimum pointer.
- Extract Minimum: Extracting the minimum element from a Fibonacci Heap involves removing the node with the minimum key value and merging its child trees with the root list. This operation takes O(log n) amortized time, where n is the number of nodes in the heap.
- Decrease Key: Decreasing the key value of a node in a Fibonacci Heap takes constant amortized time O(1). This operation may also require cutting and cascading operations to maintain the min-heap property.
Applications of Fibonacci Heaps
Fibonacci Heaps are particularly useful for algorithms that require efficient decrease key operations, such as Dijkstra’s algorithm for finding shortest paths in a graph. They are also used in some implementations of Prim’s algorithm for finding minimum spanning trees.
In conclusion, Fibonacci Heaps are a powerful data structure for priority queues that provide efficient operations such as insertion, merging, finding minimum, extracting minimum, and decreasing key. Their unique properties make them suitable for various applications where these operations are frequently performed.