Binomial Heap
Introduction
A Binomial heap is an upgraded version of Binary Heap. But why is there a need for Binomial Heap? There is a straightforward answer: operations performed by Binomial Heap are faster than the Binary Heap.
A binomial heap is the set of Binomial Trees, each satisfying the heap properties (either min-heap or max-heap).
Let’s first understand what a Binomial Tree is.
Binomial Tree:-
- The Binomial tree ‘B₀,’ which is of order 0, only consists of a single node.
- The Binomial tree ‘Bₖ’ (order K) consists of two Binomial trees of order K-1 linked together. One of them connected as a child to another tree.
Few properties of Binomial Tree of order N:-
- A tree consists of 2ⁿ nodes.
- The height of the tree is ‘N.’
- There are exactly ⁿCᵢ nodes at the depth I (i belongs to {0, 1, …., N}).
- The degree of the root is k, and the children of the root are themselves Binomial trees with order (K-1), (K-2), ….., 0 from left to right.
Now, let’s have a look at a few Binomial trees having different orders.
‘O’ here represents a node.
For k = 0
(We know for order 0, the tree consist of a single node)
O
For k = 1
(We will connect two binomial trees of order 0)
O ---- O
For k = 2
(We will connect two binomial trees of order 1)
O-----O (Order 1 Binomial Tree)
/
/
O----O (Order 1 Binomial Tree)
For k = 3
(We will connect two binomial trees of order 2)
O-----O
/
/
O----O (Order 2 Binomial Tree)
/
-------------------------------------------- Two trees of order 2 connected to form the tree of order 3.
/
O-----O
/
/
O----O (Order 2 Binomial Tree)
Refer to the below image for more understanding
Photo by algorithmitutor.com
Binomial Heap:
A binomial heap is the set of Binomial Trees, each satisfying the heap properties (either min-heap or max-heap).
How to calculate the total number of binomial trees in a binomial heap of N nodes?
Suppose we have a binomial heap of 7 nodes.
Convert it into its binary representation, i.e., 111. So, this implies that there will be three binomial trees of order 0, 1, and 2 in this binomial heap containing seven nodes.
Let’s take another example of a binomial heap of 9 nodes.
Its binary representation is 1001. Hence, there will be two binomial trees of order 0 and 3.
Hence, we can say that the total set bits are the number of binomial trees and the position of the set bit refers to the order of the binomial trees in the binomial heap.
Following is the representation of a binary heap with seven nodes.
10 -------------- 15 ------------------- 12
| / \
21 18 15
/
30
This binomial heap consists of 3 binomial trees of order 0, 1, and 2.
Operations on a Binomial Heap containing N nodes:-
- Creating a new Binomial heap: It is an O(1) process because it only makes the head of the Binomial heap with no elements attached.
- Finding the minimum value key: A binomial heap is a set of binomial trees that follow the heap property. So while finding the minimum value node, we just need to compare root values, and then we can decide which side to go, either left or right. Hence, the time complexity for this operation will be O(logN).
- Union of two binary heaps: It is the most important operation of the binomial heap, used in almost all other operations. It finds the union of two binomial heaps and then combines them into a single binomial heap. We will discuss this operation in more detail further in the blog.
- Inserting a node: We create a new binomial heap with a given node and combine the original and newly formed binomial heap by calling the union operation on them. The time complexity for this operation will be O(logN).
- Updation in the value of a node: On changing any node’s value, the heap property of the binomial tree breaks. It might be possible that after updating any node’s value, either its children’s value becomes smaller than its value or its parent value becomes more than its value(considering min-heap property). Hence, we need to make some rearrangements to that binomial tree to satisfy the heap property. The time complexity for this operation will be O(logN).
- Extracting the minimum value: First, we find the minimum value and will remove that node. We will connect all the sub-binomial trees of this removed node to form a new binomial heap and then call the union function on the newly formed and the original binomial heap. The time complexity for this operation will be O(logN).
- Deleting a node: It is similar to a binary heap’s delete operation. It first reduces the key to minus infinity and then extracts the minimum value. Its time complexity is O(logN).
Let’s discuss the representation of a binomial heap node.
Photo from javatpoint.com
The first block stores the address of the parent node.
The second block will store the key value of the node.
The third block stores the degree of the node.
The left part of the fourth block stores the address of the child, whereas the right part
holds the address of the right sibling.
Now, let’s discuss the union operation of two binomial heaps.
Given two Binomial Heaps H1 and H2, the union(H1, H2) creates a single Binomial Heap.
The first step is to merge the two Heaps in non-decreasing order of degrees.
After the simple merge, we need to ensure that there is only one Binomial Tree of any order. To do this, first, we need to combine all the Binomial Trees of the same order. We traverse the list of merged roots, and we keep track of three-pointers, prev, curr, and nextCurr. Here, ‘cur’ is the current binomial tree, ‘nextCur’ is cur’s next binomial tree, and ‘prev’ is cur’s previous binomial tree. There can be the following 4 cases when we traverse the list of roots.
Case 1: Orders of cur and nextCur are not the same. We move ahead.
In the following 3 cases, orders of cur and nextCur are the same.
Case 2: Move ahead if the order of next(nextCur)(next binomial tree to nextCur) is similar.
Case 3: If the key of cur is smaller than or equal to the key of nextCur, make nextCur a child of cur by linking it with cur.
Case 4: If the key of cur is greater, then make cur as the child of nextCur.
Implementation of the Binomial Heap:-
#include<bits/stdc++.h> trees are the same in heap |
Output:
FAQs:-
- What is a Binomial Heap?
->A binomial heap is a set of Binomial Trees, each satisfying the heap properties (either min-heap or max-heap).
- What is the main difference between ‘Binomial Heap’ and ‘Binary Heap’?
-> Binomial Heap allows the union operation much faster than Binary Heap.
- What is the final ‘ Binomial Heap ‘ order if two Binomial Heaps of order ‘K’ are joined?
-> The order of the final ‘Binomial Heap’ will be (K+1).
- What is the number of trees in the Binomial Heap of N nodes?
-> There will be log₂(N) number of trees in a Binomial Heap of N nodes.
- How many nodes are there at the depth ‘i’ of a Binomial Tree?
-> There are exactly ⁿCᵢ nodes at the depth ‘i’ where n is the number of nodes.
Key Takeaways:
In this blog we have covered the following things:
- How Binomial Heap is an upgraded version of Binary heap and how it operates faster than binary heap.
- How Binomial Heap is a set of binomial trees and each binomial tree follows heap properties.
- At last but not at least, we saw how we implemented the binomial heap.
If you want to learn more about Heaps and want to practice some questions which require you to take your basic knowledge on Heaps a notch higher, then you can visit our Guided Path for Heaps.
Until then, All the best for your future endeavors, and Keep Coding.
Comments
No comments yet
Be the first to share what you think