What is Fibonacci Heap in Data Structure? | Data Structure Tutorial

Fibonacci Heap in Data Structure

In this article, you will understand the Fibonacci Heap Data Structure in better detail.

It is a data structure that consists of a collection of trees that have a property of min heap or max heap property. These two properties are fundamental characteristics of the trees present on a Fibonacci heap. In the Fibonacci heap, the node can consist of more than two children and no children at all. It has more efficient heap operations than that supported by the binomial and binary heaps. It is known as a Fibonacci heap because the trees are constructed in a way such that a tree of order n has at least F(n+2) nodes in it.

Properties of a Fibonacci Heap

Essential Properties of a Fibonacci heap are as follows:

• The value of the parent node is always lesser than the children which means it is a set of min heap-ordered trees.
• A pointer is always maintained at the minimum element node.
• It consists of a set of marked nodes. It is called decrease key operation.
• The trees within a Fibonacci Heap are unordered but rooted. 

Node Memory Representation in a Fibonacci Heap

For faster access, the roots of the nodes are connected together. The child nodes are linked with each other with the help of the circular doubly linked list

The fundamental advantages of using a circular doubly linked are:

• O(1) time is taken to delete the node. 
• O(1) time is taken for the concatenation of two such lists

Operations on a Fibonacci Heap

Insertion

1. Create a new node for the element
2. Verify if the heap is empty.
3. If the heap is empty, set the newly created node as a root node and make it min. 
4. Otherwise, insert the node into the root and update it with min.

Find the minimum value

The minimum element is always given by the min pointer.

Union

Steps to perform the union of two Fibonacci heaps:

• Sum the roots of both the heaps
• Update the value of min by selecting the minimum key from the new root lists.

Extract Min

It is the most essential operation on a Fibonacci heap. In this, the node having the minimum value is removed from the heap and the tree is re-adjusted. 

The steps are as follows:

1. Delete the pointed min node. 
2. Set the min-pointer to the next root available in the root list. 
3. Create an array of size equal to the maximum degree of the trees in the heap before deletion.
4. Perform steps 5 to 7 until the roots having the same degree are removed. 
5. Map the degree of the min pointer to the degree of an array. 
6. Map the degree of the next root to the degree in the array. 
7. Somehow, if there are more than two mappings for the same degree, then apply the union operation to those roots. 

Complexities

The insertion case complexity is O(1).

The Find min case complexity is O(1).

The Union case complexity is O(1).

The Extract Min case complexity is O(log n)

The decreased key case complexity is O(1).

The Delete Node case complexity is O(log n)

Applications of Fibonacci Heap

• It is used to improve the asymptotic running time of Dijkstra’s algorithm.