A Binomial heap is an upgraded version of a 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 a set of Binomial Trees, each satisfying the heap properties (either min-heap or max-heap). If you dont know about Binomial Trees, don't worry we will cover that in this blog. So, let’s first understand what a Binomial Tree is.
It is an ordered tree that is recursively defined.
The Binomial tree is of two types:
The Binomial tree ‘B₀,’ in which the order of the tree is zero. This means it consists of only 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.
Order of Tree refers to the maximum number of nodes one node can have as its child nodes. For example, in a binary search tree(BST), one node can have only 2 children. Therefore the order of a BST is equal to 2.
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 order 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 depending on the values of k. In the below example, ‘O’ represents a node.
Binomial Heap
A binomial heap is a set of Binomial Trees, each satisfying the heap properties (either min-heap or max-heap). Let us see 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. The number of set bits in the binary representation directs the number of binomial trees in a binomial heap. Also, the position of set bits determines the order of each binomial tree in a heap.
In the case of 7 nodes, i.e 111, there will be three binomial trees of order 0, 1, and 2 in this binomial heap containing seven nodes. Following is the representation of a binary heap with seven nodes.
Binomial Heap with 7 Nodes
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.
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 to, 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 combines them into a single binomial heap. This is one of the most important operations in a 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, its children’s value becomes smaller than its value or its parent value becomes more than its value(considering min-heap property). Hence, we must rearrange 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).
Representation of a Binomial Heap Node
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.
The right part holds the address of the right sibling.
Union Operation of Two Binomial Heaps
When you are provided with two different binomial heaps (say A, B), and your task is to create a single Binomial Heap from it, that is what we call a union. Union operation is a major operation considering Binomial Heap because it implements various other operations such as Insert, Delete, Update extract min.
To perform union operation, we need to perform the following steps:
First, need to merge given two heaps in non-increasing orders of their degrees.
Now, combine all binomial heaps of the same order into one. This can be done by keeping track of three-pointers. These are - prev, curr, and next. Here, the ‘curr’ pointer points to the current binomial tree, ‘next’ is the binomial tree next to current binomial tree, and ‘prev’ is the binomial tree previous to the current binomial tree. There can be four different cases while traversing through the list of roots. These are mentioned below:-
Orders of curr and next are not the same. We move ahead the pointers. In the remaining three cases, orders of curr and next are the same.
If the orders of curr, next and siblingof next are same then move ahead the pointers.
If the orders of curr and next are same and not equal to the order of sibling of next and the key value of curr is smaller than or equal to the key value of next, make next a child of curr by linking it with curr.
If the key value of curr is greater, then make curr equals to the child of next.
From the heap obtained in step 1, node 4 and 6 are of same degree so using case 3 node 6 become child of node 4. Similarly using case 3 heap 8,15 becomes child of heap 7,25. Now the heap obtained looks like the image below:
Order of curr and next are not same. So using case 1, we can move ahead.
Now the heap of node 7 and 18 can be merged using case 3 again. It will look like:
As we know the heaps should be in increasing order so swap heaps with nodes 7. Hence, considering all the above cases, the union for above example is as follows:
Implementation of the Binomial Heap
Let us now understand the implementation of Binomial Heap in C++.
#include<bits/stdc++.h>
using namespace std;
//Node for Binomial Tree
struct BNode
{
//Key value
int key;
//Order
int order;
//sibling, parent and child pointers.
BNode *sibling, *parent, *child;
//Parameterised Constructor
BNode(int key)
{
this -> key = key;
this -> order = 0;
this -> sibling = this -> parent = this -> child = NULL;
}
};
class BHeap
{
//Node that points to the leftmost binomial tree.
BNode *head;
//Node that points to the minimum value.
BNode *min;
//Function to combine two trees.
void combineTrees(BNode *root1, BNode *root2)
{
//Making sure that root2 has smaller key value
if(root1->key < root2->key){
swap(root1,root2);
}
/*
Assuming root1->key >= root2->key
then root2 must be parent of root1.
*/
root1 -> parent = root2;
root1 -> sibling = root2 -> child;
root2 -> child = root1;
//Increasing the order of second tree.
root2 -> order = root2 -> order + 1;
}
/*
This function will merge given two heaps
in non- increasing value of their orders/degrees.
*/
BNode* combineHeaps(BHeap *heap1, BHeap *heap2)
{
//Temporary Nodes to merge two heads.
BNode *temp1 = new BNode(0);
BNode *temp2 = temp1;
//Initializing the roots of each head.
BNode *root1 = heap1 -> head;
BNode *root2 = heap2 -> head;
//if one of the roots is null return other one.
if (root1 == NULL) return root2;
if (root2 == NULL) return root1;
//Combining the roots to make a new heap in increasing value of orders.
while (root1 != NULL || root2 != NULL)
{
if (root1 == NULL)
{
temp2 -> sibling = root2;
temp2 = temp2 -> sibling;
root2 = root2 -> sibling;
}
else if (root2 == NULL)
{
temp2 -> sibling = root1;
temp2 = temp2 -> sibling;
root1 = root1 -> sibling;
}
else
{
if (root1 -> order < root2 -> order)
{
temp2 -> sibling = root1;
temp2 = temp2 -> sibling;
root1 = root1 -> sibling;
}
else
{
temp2 -> sibling = root2;
temp2 = temp2 -> sibling;
root2 = root2 -> sibling;
}
}
}
return (temp1 -> sibling);
}
public:
//Empty Heap Constructor
BHeap() {
this -> head = NULL;
}
//binomial heap with given node.
BHeap(BNode* root){
this -> head = root;
}
//Return true or false based on if the heap is empty or not.
bool isEmpty(){
return (this -> head == NULL);
}
void insert(BNode* root){
BHeap* newHeap=new BHeap(root);
this -> unionHeap(newHeap);
}
void unionHeap(BHeap *heap)
{
//New heap to hold the union of two heaps.
BHeap *heap_final = new BHeap();
//Merging two heaps.
heap_final -> head = combineHeaps(this, heap);
//If both heaps are empty, heap_final will also be empty.
if (heap_final -> head == NULL)
{
this -> head = NULL;
this -> min = NULL;
return;
}
//three pointers prev, curr and next.
BNode *prev = NULL;
BNode *curr = heap_final -> head;
BNode *next = curr -> sibling;
//checking all four cases for curr and next pointer.
while (next != NULL)
{
//Case 1: when order[curr]!=order[next]
if (curr -> order != next -> order){
prev = curr;
curr = next;
}
//Case 2: when order[curr]==order[next]==order[sibling(next)]
else if( curr -> order == next -> order && next -> sibling != NULL && next -> sibling -> order == curr -> order){
prev = curr;
curr = next;
}
//Case 3
else if (curr -> key <= next -> key){
curr -> sibling = next -> sibling;
combineTrees(next, curr);
}
//Case 4
else{
if (prev == NULL) heap_final -> head = next;
else prev -> sibling = next;
combineTrees(curr, next);
curr = next;
}
next = curr -> sibling;
}
this -> head = heap_final -> head;
//Updating minimum node.
this -> min = heap_final -> head;
curr = this -> head;
while (curr != NULL)
{
if (curr -> key < this -> min -> key) this -> min = curr;
curr = curr -> sibling;
}
}
BNode* first()
{
return this -> min;
}
BNode* extractMin()
{
// Minimum Node
BNode *mini = this -> first();
// Delete minimum node from the list of head
BNode *prev = NULL;
BNode *curr1 = this -> head;
while (curr1 != mini)
{
prev = curr1;
curr1 = curr1 -> sibling;
}
/*
If prev is null it means starting node is itself minimum.
So, we update head to sibling of head.
*/
if (prev == NULL) this -> head = curr1 -> sibling;
//Removing the minimum node from the heap.
else prev -> sibling = curr1 -> sibling;
// Reverse the list of minimum node children
BNode *RevNode = NULL;
BNode *curr2 = mini -> child;
while (curr2 != NULL)
{
BNode *next = curr2 -> sibling;
curr2 -> sibling = RevNode;
RevNode = curr2;
curr2 = next;
}
/*
Merge the two heaps, the original one and the one
containing the children of minimum node.
*/
BHeap *temp = new BHeap();
temp -> head = RevNode;
this -> unionHeap(temp);
//return minimum node.
return mini;
}
void decreaseKey(BNode *root, int val)
{
//Checking if the current val is less than root's value or not.
if(val > root->key){
cout<<"Error! New value greater than current key!\n";
return;
}
//Updating the root
root -> key = val;
//Temporary nodes to update the minimum to the top of the heap.
BNode *temp1 = root;
BNode *temp2 = temp1 -> parent;
while (temp2 != NULL && temp1 -> key < temp2 -> key)
{
// Swapping value of parent's key and current key.
swap(temp1 -> key, temp2 -> key);
temp1 = temp2;
//Updating Parent node
temp2 = temp1 -> parent;
}
//Updating the minimum node in the heap.
if (temp1 -> key < this -> min -> key) this -> min = temp1;
}
void Delete(BNode *root)
{
decreaseKey(root, INT_MIN);
extractMin();
}
//Level order traversal of the tree.
void printTree(BNode* root){
if(root==nullptr){
return;
}
queue<BNode*> q;
q.push(root);
while (!q.empty()) {
BNode* node = q.front();
q.pop();
cout<<node->key<<" ";
if (node->child != nullptr) {
BNode* temp = node->child;
while (temp != nullptr) {
q.push(temp);
temp = temp->sibling;
}
}
}
}
void printHeap() {
BNode* curr = head;
while (curr != nullptr) {
cout<<"B"<<curr->order<<endl;
cout<<"There are "<<pow(2, curr->order)<<" nodes in this binomial tree"<<endl;
cout<<"The level order traversal of the tree is ";
this->printTree(curr);
curr = curr->sibling;
cout<<endl<<endl;
}
}
};
int main()
{
BHeap *heap1 = new BHeap();
heap1->insert(new BNode(2));
heap1->insert(new BNode(7));
heap1->insert(new BNode(13));
heap1->insert(new BNode(8));
heap1->insert(new BNode(1));
cout<<"Printing Binomial Heap !!!\n\n";
heap1->printHeap();
cout<<"Extracting Minimum value from the Heap.\n";
cout<<"Minimum key is "<<(heap1 -> extractMin()) -> key<<endl<<endl;
cout<<"Printing Binomial Heap After Extracting Minimum Value!!!\n\n";
heap1->printHeap();
cout<<"Extracting Minimum value from the Heap.\n";
cout<<"Minimum key is "<<(heap1 -> extractMin()) -> key<<endl<<endl;
cout<<"Printing Binomial Heap After Extracting Minimum Value!!!\n\n";
heap1->printHeap();
}
Output
Printing Binomial Heap !!!
B0
There are 1 nodes in this binomial tree
The level order traversal of the tree is 1
B2
There are 4 nodes in this binomial tree
The level order traversal of the tree is 2 8 7 13
Extracting Minimum value from the Heap.
Minimum key is 1
Printing Binomial Heap After Extracting Minimum Value!!!
B2
There are 4 nodes in this binomial tree
The level order traversal of the tree is 2 8 7 13
Extracting Minimum value from the Heap.
Minimum key is 2
Printing Binomial Heap After Extracting Minimum Value!!!
B0
There are 1 nodes in this binomial tree
The level order traversal of the tree is 7
B1
There are 2 nodes in this binomial tree
The level order traversal of the tree is 8 13
Frequently Asked Questions
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.
Conclusion
In this blog, we have covered the following: how Binomial Heap is an upgraded version of Binary heap and how it operates faster than binary heap. We also discussed how Binomial Heap is a set of binomial trees, and each binomial tree follows heap properties. Last but not least, we saw how we implemented the binomial heap.