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

In this article, you will learn the following concepts:

• What is Fibonacci Heap?
• What are the Properties of a Fibonacci Heap?
• How to represent the memory of the Node in a Fibonacci Heap?
• What Operations can be done on a Fibonacci Heap?

What is Fibonacci Heap?

A Fibonacci heap is a data structure that comprises a collection of trees that will follow the property of a min heap or max heap. The min heap and max heap are the characteristics of the trees present on a Fibonacci heap. In a Fibonacci heap, a node can have either more than two heap operations or no children at all. Also, it has more efficient heap operations than that supported by the binomial and binary heaps. The Fibonacci heap is known as the Fibonacci heap because the trees are formulated in a manner 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:

• Fibonacci Heap is a set of min heap-ordered trees. (The parent node is always smaller than the children node)
• A pointer is always maintained at the minimum element node. 
• It consists of a set of marked nodes. It is known as a Decrease key operation. 
• The trees within a Fibonacci heap are rooted but unordered.

Memory Representation of the Nodes in a Fibonacci Heap

The roots of every tree are linked with each other for faster access. The child nodes of a parent node are clubbed with each other through a circular doubly linked list. The two main advantages of using a circular doubly linked list:

• It takes O(1) time to delete the node from the tree.
• The merging of two such lists takes the time O(1).

Operations on a Fibonacci Heap are:

• Insertion:

Adding a node into an already existing heap is done with the help of the following steps:

• Create a new node for an item.
• Now, check if the heap is empty or full. 
• If the heap is empty, consider the new node as a root node and make it min.
• Else, insert the node into the root node and update the value of the min.

Find Min

The value of the minimum element is always given by the min pointer.

Union

To do the union of two Fibonacci heaps comprises the following steps:

• Merge the roots of both the heaps
• Update the value of the 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 operation, the node having the minimum value is removed from the heap and the tree is re-adjusted.

The following steps are:

• Delete the value of the min node. 
• Set the value of the min-pointer to the next root in the root list. 
• Create an array of size equal to the maximum degree of the trees in a heap before the deletion of an element.
• Repeat the next three steps again and again until there are no multiple roots with the same degree.
• Map the degree of the min-pointer to the degree in the array.
• Map the degree of the next root to the degree in the array.
• The mappings are done for the same degree, then apply the union operation to those roots such that the min-heap property is maintained

The application of the Fibonacci heap is to improve the asymptotic running time of Dijkstra's algorithm.