Last Updated on March 2, 2023 by Prepbytes
In this section, we will discuss the Fibonacci heap, properties of the Fibonacci heap, application of the Fibonacci heap, Fibonacci heap operation, time complexity in a Fibonacci heap, and implementation of extract min operation in a Fibonacci heap.
What is Fibonacci Heap?
The Fibonacci heap is a type of data structure that can be used to implement a priority queue. The key feature of this type of heap is its efficient merging of elements, which allows for fast and efficient processing of elements. In addition, Fibonacci heaps provide an amortized O(1) time complexity for operations such as insertions, deletions, and finding the minimum element, making them highly efficient in comparison to other types of data structures for priority queues.
Properties of the Fibonacci Heap
Given below are the properties of the fibonacci heap:
- Min-heap property: Each node has a key that is less than or equal to its children.
- Structure: A collection of trees that are min heaps, where a tree is either a single node or a collection of min heaps that are all rooted at a single node.
- Amortized time: O(1) time for inserting a node and O(log n) time for deleting the minimum node.
- Linking: When two trees of the same rank are combined, they are linked by making one tree a subtree of the other.
- Consolidation: The process of combining trees of the same rank during a delete operation.
- Rank: Number of children a node has.
- Marking: A node can be marked if it has lost a child since the last time it was made the child of another node.
Application of Fibonacci Heap
Fibonacci heap has a wide range of applications in computer science, particularly in algorithms related to:
- Graph algorithms: It is used in algorithms such as Dijkstra’s shortest path algorithm and Prim’s algorithm for finding minimum spanning trees.
- Network flow algorithms: Fibonacci heap is used in algorithms such as the Edmonds-Karp algorithm for finding maximum flow in a network.
- Heap sort: It is used in heap sort algorithms as a more efficient alternative to binary heaps.
- Mathematical optimization: Fibonacci heap is used in optimization problems to efficiently find the minimum or maximum element in a set.
- Task scheduling: It is used in scheduling algorithms for efficient resource allocation and task prioritization.
- Computational geometry: It is used in geometric algorithms to efficiently compute intersections, closest pairs, and convex hulls.
In addition to these applications, the Fibonacci heap is also used in other areas where efficient priority queues are required, such as image processing and data compression.
Memory Representation of the Nodes
In a Fibonacci heap, each node in the heap contains the following fields:
- Key: the value of the node.
- Degree: the number of children the node has.
- Mark: a flag that indicates whether the node has lost a child since it was added to the root list.
- Parent: a pointer to the parent node.
- Child: a pointer to the first child node.
- Left: a pointer to the node to the left of the current node in the doubly linked list.
- Right: a pointer to the node to the right of the current node in the doubly linked list.
The nodes in a Fibonacci heap are organized as a collection of trees, with each tree having a root node that is linked in a circular doubly linked list with the other roots there are two main advantages of using a circular doubly linked list. (deleting a node from tree takes O(1) time and the concatenation of two such list takes O(1) time.
Fibonacci Heap Operations:
MakeHeap: This operation creates an empty heap. A heap is represented by a single tree rooted at the minimum element in the heap. Initially, this tree is empty.
Code Implementation:
# Fibonacci Heap in python
import math
# Creating fibonacci tree
class FibonacciTree:
def __init__(self, value):
self.value = value
self.child = []
self.order = 0
# Adding tree at the end of the tree
def add_at_end(self, t):
self.child.append(t)
self.order = self.order + 1
# Creating Fibonacci heap
class FibonacciHeap:
def __init__(self):
self.trees = []
self.least = None
self.count = 0
# Insert a node
def insert_node(self, value):
new_tree = FibonacciTree(value)
self.trees.append(new_tree)
if (self.least is None or value < self.least.value):
self.least = new_tree
self.count = self.count + 1
# Get minimum value
def get_min(self):
if self.least is None:
return None
return self.least.value
# Extract the minimum value
def extract_min(self):
smallest = self.least
if smallest is not None:
for child in smallest.child:
self.trees.append(child)
self.trees.remove(smallest)
if self.trees == []:
self.least = None
else:
self.least = self.trees[0]
self.consolidate()
self.count = self.count - 1
return smallest.value
# Consolidate the tree
def consolidate(self):
aux = (floor_log(self.count) + 1) * [None]
while self.trees != []:
x = self.trees[0]
order = x.order
self.trees.remove(x)
while aux[order] is not None:
y = aux[order]
if x.value > y.value:
x, y = y, x
x.add_at_end(y)
aux[order] = None
order = order + 1
aux[order] = x
self.least = None
for k in aux:
if k is not None:
self.trees.append(k)
if (self.least is None
or k.value < self.least.value):
self.least = k
def floor_log(x):
return math.frexp(x)[1] - 1
fibonacci_heap = FibonacciHeap()
fibonacci_heap.insert_node(7)
fibonacci_heap.insert_node(3)
fibonacci_heap.insert_node(17)
fibonacci_heap.insert_node(24)
print('the minimum value of the fibonacci heap: {}'.format(fibonacci_heap.get_min()))
print('the minimum value removed: {}'.format(fibonacci_heap.extract_min())) Output:
the minimum value of the fibonacci heap: 3
the minimum value removed: 3Insertion: This operation adds a new element to the heap. The new element is added as a single tree rooted at the new element and linked to the existing trees in the heap. The minimum element in the heap remains unchanged.
- For the element, create a new node.
- Check if the heap is empty.
- Set the new node as a root node and minify it if the heap is empty.
- If not, update by adding the node to the root list.
Union: This operation merges two heaps into one. The two heaps are represented by two trees rooted at the minimum elements in each heap. The trees are linked together, and the minimum element in the combined heap is found.
Extract-Min: This operation removes and returns the minimum element from the heap. The minimum element is the root of the tree that represents the heap. To extract the minimum element, the tree rooted at the minimum element is cut into a collection of trees, and the new minimum element is found. The new minimum element is then returned.
The minimum node in a Fibonacci heap is the node with the minimum key value and is always the root of the tree. To extract the minimum node, the following steps are taken:
- Save the minimum node
- Now we remove the minimum node from the root list.
- If the minimum node has children, add them to the root list.
- If the root list has only one node, return the minimum node.
- If the root list has more than one node, merge the root list into one tree.
- Mark the remaining trees for consolidation and set the minimum node to the tree with the minimum key.
- Repeat steps 4-6 until there is only one tree in the root list.
- Return the saved minimum node.
Implementation of extract min operation
Here we will apply the extract min operation on the heap below.
Now we delete the min node and add all its child nodes to the root list and set the min-pointer to the next root in the root list.
The maximum degree in the tree is 3 (no of the child here is maximum degree) to create an array of size 4 and map the degree of the next roots, here indexes of an array is referred to the degree of a particular node.
Here if we observe 23 have zero degrees (means No child) and 17 nodes have one degree(have single child 30) now we unite the node which has the same degree
7 and 23 have the same degree so we unite them and now 7 and 17 have the same degree so we unite them also.
Now 7 and 24 have the same degree, so we unite them also
Now 52 and 21 have the same degree which is zero so we unite them
Now similarly we have unit 21 and 18 because they have the same degree
After mapping, we find now all the root nodes have a different degree and we got our final heap.
Decrease-Key: This operation decreases the value of a key within the heap. The value of a key can be decreased by replacing the tree rooted at the key with a new tree rooted at the new value. The new tree is linked to the existing trees in the heap. The minimum element in the heap remains unchanged.
Delete: This operation removes a specific element from the heap. The element is removed by decreasing its key to negative infinity and then extracting the minimum element from the heap. The extracted element is guaranteed to be the element that was deleted.
Code Implementation:
# Fibonacci Heap in python
import math
# Creating fibonacci tree
class FibonacciTree:
def __init__(self, value):
self.value = value
self.child = []
self.order = 0
# Adding tree at the end of the tree
def add_at_end(self, t):
self.child.append(t)
self.order = self.order + 1
# Creating Fibonacci heap
class FibonacciHeap:
def __init__(self):
self.trees = []
self.least = None
self.count = 0
# Insert a node
def insert_node(self, value):
new_tree = FibonacciTree(value)
self.trees.append(new_tree)
if (self.least is None or value < self.least.value):
self.least = new_tree
self.count = self.count + 1
# Get minimum value
def get_min(self):
if self.least is None:
return None
return self.least.value
# Extract the minimum value
def extract_min(self):
smallest = self.least
if smallest is not None:
for child in smallest.child:
self.trees.append(child)
self.trees.remove(smallest)
if self.trees == []:
self.least = None
else:
self.least = self.trees[0]
self.consolidate()
self.count = self.count - 1
return smallest.value
# Consolidate the tree
def consolidate(self):
aux = (floor_log(self.count) + 1) * [None]
while self.trees != []:
x = self.trees[0]
order = x.order
self.trees.remove(x)
while aux[order] is not None:
y = aux[order]
if x.value > y.value:
x, y = y, x
x.add_at_end(y)
aux[order] = None
order = order + 1
aux[order] = x
self.least = None
for k in aux:
if k is not None:
self.trees.append(k)
if (self.least is None
or k.value < self.least.value):
self.least = k
def floor_log(x):
return math.frexp(x)[1] - 1
fibonacci_heap = FibonacciHeap()
fibonacci_heap.insert_node(7)
fibonacci_heap.insert_node(3)
fibonacci_heap.insert_node(17)
fibonacci_heap.insert_node(24)
print('the minimum value of the fibonacci heap: {}'.format(fibonacci_heap.get_min()))
print('the minimum value removed: {}'.format(fibonacci_heap.extract_min())) Time Complexity in Fibonacci Heap:
The time complexity of operations in a Fibonacci Heap is as follows:
- MakeHeap: O(1)
- Insert: O(1)
- Extract-Min: O(log n), where n is the number of elements in the heap.
- Union: O(1)
- Decrease-Key: O(1) amortized
- Delete: O(log n) amortized
It is worth noting that the amortized time complexity refers to an average-case analysis over a sequence of operations, and is a way of analyzing algorithms that perform differently on different inputs. The actual time complexity of individual operations can be higher, but the average time complexity over a sequence of operations is guaranteed to be O(1) or O(log n) amortized.
In general, Fibonacci Heaps have a very good time complexity for their operations, which makes them efficient for use in many algorithms. For example, they are used in Dijkstra’s algorithm for finding the shortest path in a graph, and in Kruskal’s algorithm for finding a minimum spanning tree in a graph.
Conclusion
The merging of elements is performed by linking two trees of equal degrees into a single tree, with the smallest value becoming the root. This merging process ensures that the number of trees in the heap remains small, which contributes to the fast processing time of the heap.
Fibonacci heaps have numerous applications in areas such as graph algorithms and computational geometry, where they are used to efficiently find minimum spanning trees and to solve problems related to finding the shortest distance between two points. They are also used in other areas where efficient priority queues are required, such as scheduling and resource allocation.
In conclusion, Fibonacci heap is a highly efficient data structure for implementing priority queues, providing fast and efficient processing of elements, and allowing for the quick merging of elements.