Fibonacci Heap

---

In the world of computer science, data structures are essential for organizing and managing data efficiently. Among the many data structures, the Fibonacci Heap stands out due to its impressive amortized time complexity for various operations. It is particularly useful when working with priority queues, which are a vital component in algorithms such as Dijkstra’s shortest path and Prim's minimum spanning tree.

---

Table of Contents

1. What is a Fibonacci Heap?
2. Key Properties of Fibonacci Heaps
3. Basic Operations of Fibonacci Heap
4. Time Complexity of Fibonacci Heap Operations
5. Sample Fibonacci Heap Code Implementation
6. Use Cases of Fibonacci Heaps
7. Conclusion

---

1. What is a Fibonacci Heap?

A Fibonacci Heap is a type of heap data structure that consists of a collection of min-heaps organized in a more flexible way. It was introduced by Michael L. Fredman and Robert E. Tarjan in 1984 and is a highly efficient data structure for priority queues. The Fibonacci Heap is named after the Fibonacci numbers because of its structure, which resembles a Fibonacci tree.

Fibonacci Heaps offer better time complexities for several operations than traditional binary heaps, making them particularly advantageous in scenarios where multiple heap operations need to be performed in sequence, such as in network routing algorithms or graph traversal.

---

2. Key Properties of Fibonacci Heaps

Fibonacci Heaps have several key properties that distinguish them from other heap data structures:

• A collection of trees: A Fibonacci Heap is a collection of trees that satisfy the min-heap property (the value of each node is greater than or equal to the value of its parent).
• Lazy merging: The merging of two heaps is done lazily, meaning it’s postponed until necessary, improving performance.
• Amortized time complexity: Fibonacci Heaps offer efficient amortized time complexities, meaning that over a sequence of operations, the average time per operation is low.

---

3. Basic Operations of Fibonacci Heap

Fibonacci Heaps support a variety of operations, each with different time complexities. Some of the key operations include:

• Insert(x): Insert a new element x into the heap.
• Minimum(): Retrieve the minimum element from the heap.
• Extract-Min(): Remove and return the minimum element from the heap.
• Union(): Merge two Fibonacci Heaps into one.
• Decrease-Key(x, k): Decrease the key of a specific element x to a new value k.
• Delete(x): Delete a specific element x from the heap.

---

4. Time Complexity of Fibonacci Heap Operations

The Fibonacci Heap provides the following amortized time complexities for its operations:

• Insert(x): O(1) – This operation can be done in constant time.
• Minimum(): O(1) – Accessing the minimum element is also done in constant time.
• Extract-Min(): O(log n) amortized – The most expensive operation, but it still remains logarithmic in the amortized sense.
• Union(): O(1) – Union of two heaps is a constant-time operation.
• Decrease-Key(x, k): O(1) amortized – Decreasing a key can be done efficiently.
• Delete(x): O(log n) amortized – Deleting an element requires a logarithmic time in the worst case.

The Fibonacci Heap outperforms other heaps, such as binary heaps, for algorithms like Dijkstra’s shortest path and Prim's minimum spanning tree, where many Decrease-Key and Extract-Min operations are required.

---

5. Sample Fibonacci Heap Code Implementation (Python)

Let’s now take a look at a basic implementation of the Fibonacci Heap in Python.

class FibonacciHeapNode:
    def __init__(self, key):
        self.key = key
        self.degree = 0
        self.parent = None
        self.child = None
        self.mark = False
        self.next = self
        self.prev = self

class FibonacciHeap:
    def __init__(self):
        self.min = None
        self.total_nodes = 0

    def insert(self, key):
        new_node = FibonacciHeapNode(key)
        if self.min is None:
            self.min = new_node
        else:
            # Linking new node into the root list
            self._link(self.min, new_node)
            if key < self.min.key:
                self.min = new_node
        self.total_nodes += 1

    def _link(self, node1, node2):
        # Connect node2 to node1's next
        node1_next = node1.next
        node1.next = node2
        node2.prev = node1
        node2.next = node1_next
        node1_next.prev = node2

    def extract_min(self):
        if self.min is None:
            return None

        min_node = self.min
        if min_node.child is not None:
            child = min_node.child
            while True:
                next_child = child.next
                child.prev = self.min.prev
                self.min.prev.next = child
                child.next = self.min
                self.min.prev = child
                child = next_child
                if child == min_node.child:
                    break

        self.min = min_node.next
        self.total_nodes -= 1
        return min_node.key

    def minimum(self):
        if self.min is None:
            return None
        return self.min.key

Explanation of the Code:

1. FibonacciHeapNode Class: Represents a node in the Fibonacci Heap. It contains information like the node's key, degree, and links to parent and child nodes.
2. FibonacciHeap Class: Manages the heap, including inserting new nodes, extracting the minimum node, and maintaining the heap structure.
3. insert() Method: Inserts a new element into the Fibonacci Heap. It handles the root list and ensures that the minimum node is correctly updated.
4. extract_min() Method: Removes and returns the minimum element from the heap, which may involve consolidating the heap’s trees.

---

6. Use Cases of Fibonacci Heaps

Fibonacci Heaps are especially useful in the following scenarios:

• Graph Algorithms: Due to their efficient decrease-key operation, Fibonacci Heaps are ideal for algorithms like Dijkstra’s shortest path and Prim’s minimum spanning tree, which involve many decrease-key operations.
• Priority Queues: Any system requiring frequent insertion and extraction of the minimum element can benefit from the use of Fibonacci Heaps.
• Network Flow Algorithms: Fibonacci Heaps are helpful in network flow algorithms that deal with large graphs and require efficient heap operations.

---

---