Binary Heap:
Binary heap is a complete tree i.e. All the levels of the tree are completely filled except the leaf nodes or last level and have all keys on the left. Due to this property, Binary heaps are suitable to be stored in an array.
A binary heap is either a min-heap or a max heap.
In the min-heap, the value at the root node is smaller than all the nodes present in the binary heap, and in the max heap, the value at the root node is greater than all the nodes present in the binary heap.
Binomial Heap:
Binomial heap is an extension of binary heaps. Binomial heaps provide faster operations.
A binomial heap is a collection of binomial trees.
So what is a binomial tree?
A binomial tree of order 0 has 1 node only. We can construct a binomial tree of k order by taking two binomial trees of order k-1 and making one tree as the leftmost child or other.
Some properties of order k binomial tree:
- The binomial tree has exactly 2k nodes.
- The binomial tree has a depth of k.
- The root of the binomial tree has degree k and children of the root node are also binomial trees.
A binomial heap is a set of binomial trees where each binomial tree follows the min-heap property.
Fibonacci Heap:
Fibonacci heap is a collection of trees that follows the property of min heap or max heap. Fibonacci heaps can have any shape even if all trees can have a single node. In Fibonacci heaps, we’ll maintain a pointer to a minimum value i.e. root of the tree.
All tree roots are connected using a circular doubly linked. Therefore, we can access all of them using a single pointer.
Example:
This article tried to discuss the Difference between binary heap, binomial heap, and Fibonacci heap. Hope this blog helps you understand the concept. To practice problems on Heap you can check out MYCODE | Competitive Programming – Heaps.