Introduction
Fibonacci heap is a variety of Data structures that contains a collection of trees and follows the property of Priority-Queue Data Structures (often referred to as Heap).
In Fibonacci, Heap Node can have zero, two, or more children. The reason why we use the Fibonacci heap is that it has a better and more efficient heap operation as compared to the remaining two heaps.
Also see, Implementation of Heap
Three major types of Heap
- Binary Heap
- Binomial Heap
- Fibonacci Heap
Binary Heap
It is a Binary Tree with the following properties:
- It should be a complete tree.
- It should either be a Min Heap or a Max Heap.
- Min Heap: Root element minimum in the Tree.
-
Max Heap: Root element maximum in the Heap.
Binomial Heap
Binomial Heap is a collection of Binomial Tree in which every Binomial Tree follows the Min Heap property.
A maximum of one Binomial Tree is Permitted of any degree.
Q:-What is Binomial Tree?
A binomial tree of order zero has 1 node. A binomial tree of order ‘k’ may be built by using taking two binomial trees of order k-1 and making one as a leftmost child or other.
A binomial tree of order okay has the following residences.
- It has precisely 2^k nodes.
- It has depth as ‘k’.
- There are precisely ^kci nodes at intensity i for i = 0, 1, . . . , ok.
-
The basis has degree k and children of the root are themselves binomial Trees with order k-1, k-2,.. Zero from left to right.
Fibonacci Heap
Fibonacci Heap tree is a Collection tree built using the min-heap and max-heap Property of Priority Queue.
The notable thing about the Fibonacci heap is that the Fibonacci heap tree can have any shape even if all three can have single nodes.
Note:
In the case of implementation, the Fibonacci heap is best in terms of time complexity, and it beats Binary Heap and Binomial Heap in time complexity.
Also Read, Prefix Sum Array
24+ registered 
