Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Binomial Tree
3.
Binomial Heap 
4.
Operations on a Binomial Heap containing N nodes
5.
Representation of a Binomial Heap Node
6.
Union Operation of Two Binomial Heaps
7.
Implementation of the Binomial Heap
8.
Frequently Asked Questions
8.1.
What is a Binomial Heap?
8.2.
What is the main difference between ‘Binomial Heap’ and ‘Binary Heap’?
8.3.
What is the final ‘ Binomial Heap ‘ order if two Binomial Heaps of order ‘K’ are joined?
8.4.
What is the number of trees in the Binomial Heap of N nodes?
8.5.
How many nodes are there at the depth ‘i’ of a Binomial Tree?
9.
Conclusion
Last Updated: Mar 27, 2024
Hard

Binomial Heap

Author Rhythm Jain
0 upvote
gp-icon
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
gp-badge
Earn badges and level up

Introduction

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.

OG image

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.

Also Read, Prefix Sum Array and Data Structure

Binomial Tree

It is an ordered tree that is recursively defined.

The Binomial tree is of two types: 

  1. The Binomial tree ‘B₀,’ in which the order of the tree is zero. This means it consists of only a single node. 
  2. 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:-

  1. A tree consists of 2ⁿ nodes.
  2. The height of the tree is ‘N.’
  3. There are exactly ⁿCᵢ nodes at the depth I (i belongs to {0, 1, …., N}).
  4. 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 Trees of Order 0 and 1.
Binomial Trees of Order 2.
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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

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

  1. 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.
     
  2. 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).
     
  3. 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.
     
  4. 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).
     
  5. Updation in the value of a nodeOn 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).
     
  6. 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).
     
  7. 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

Representation of a Binary Heap

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.  
Union of Two Heaps: Merge
  • 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:- 

    1. 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. 
       
    2. If the orders of currnext and sibling of next are same then move ahead the pointers.
       
    3. 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. 
       
    4. If the key value of curr is greater, then make curr equals to the child of next.
       
Union of Two Heaps: Step 2

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:

Union of Two Heaps: Step 3

Order of curr and next are not same. So using case 1, we can move ahead.

Union of Two Heaps: Step 4


Now the heap of node 7 and 18 can be merged using case 3 again. It will look like:

Union of Two Heaps: Step 5

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:

Union of Two Heaps: Final Heap

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.

Check out this problem - Reverse Nodes In K Group

Here are a few related articles you can refer to

Please refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc. Also, enroll in our courses and refer to the mock test and problems available. Have a look at the interview experiences and interview bundle for placement preparations.

Keep Coding.

Previous article
Time Complexity of building a heap
Next article
Fibonacci Heap
Guided path
Free
gridgp-icon
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
gp-badge
Earn badges and level up
Live masterclass