Binomial Heap in Data Structure

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.

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

What is Binomial Tree?

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.

What is 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:-
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 curr, next 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.

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++, Java, Python, C#, Javascript.

C++
Java
Python
C#
JavaScript

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();
}

You can also try this code with Online C++ Compiler

Run Code

Java

import java.util.LinkedList;
import java.util.Queue;

class BNode {
    int key;
    int order;
    BNode sibling, parent, child;

    BNode(int key) {
        this.key = key;
        this.order = 0;
        this.sibling = this.parent = this.child = null;
    }
}

class BHeap {
    BNode head;
    BNode min;

    public BHeap() {
        this.head = null;
    }

    public BHeap(BNode root) {
        this.head = root;
    }

    private void combineTrees(BNode root1, BNode root2) {
        if (root1.key < root2.key) {
            BNode temp = root1;
            root1 = root2;
            root2 = temp;
        }
        root1.parent = root2;
        root1.sibling = root2.child;
        root2.child = root1;
        root2.order += 1;
    }

    private BNode combineHeaps(BHeap heap1, BHeap heap2) {
        BNode temp1 = new BNode(0);
        BNode temp2 = temp1;
        BNode root1 = heap1.head;
        BNode root2 = heap2.head;

        if (root1 == null) return root2;
        if (root2 == null) return root1;

        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 void insert(BNode root) {
        BHeap newHeap = new BHeap(root);
        unionHeap(newHeap);
    }

    public void unionHeap(BHeap heap) {
        BHeap heapFinal = new BHeap();
        heapFinal.head = combineHeaps(this, heap);

        if (heapFinal.head == null) {
            this.head = null;
            this.min = null;
            return;
        }

        BNode prev = null;
        BNode curr = heapFinal.head;
        BNode next = curr.sibling;

        while (next != null) {
            if (curr.order != next.order) {
                prev = curr;
                curr = next;
            } else if (curr.order == next.order && next.sibling != null && next.sibling.order == curr.order) {
                prev = curr;
                curr = next;
            } else if (curr.key <= next.key) {
                curr.sibling = next.sibling;
                combineTrees(next, curr);
            } else {
                if (prev == null) heapFinal.head = next;
                else prev.sibling = next;
                combineTrees(curr, next);
                curr = next;
            }
            next = curr.sibling;
        }

        this.head = heapFinal.head;
        this.min = heapFinal.head;
        curr = this.head;
        while (curr != null) {
            if (curr.key < this.min.key) this.min = curr;
            curr = curr.sibling;
        }
    }

    public BNode extractMin() {
        BNode mini = this.min;
        BNode prev = null;
        BNode curr1 = this.head;

        while (curr1 != mini) {
            prev = curr1;
            curr1 = curr1.sibling;
        }

        if (prev == null) this.head = curr1.sibling;
        else prev.sibling = curr1.sibling;

        BNode revNode = null;
        BNode curr2 = mini.child;
        while (curr2 != null) {
            BNode next = curr2.sibling;
            curr2.sibling = revNode;
            revNode = curr2;
            curr2 = next;
        }

        BHeap temp = new BHeap();
        temp.head = revNode;
        this.unionHeap(temp);

        return mini;
    }

    public void printTree(BNode root) {
        if (root == null) return;

        Queue<BNode> q = new LinkedList<>();
        q.add(root);
        while (!q.isEmpty()) {
            BNode node = q.poll();
            System.out.print(node.key + " ");

            if (node.child != null) {
                BNode temp = node.child;
                while (temp != null) {
                    q.add(temp);
                    temp = temp.sibling;
                }
            }
        }
    }

    public void printHeap() {
        BNode curr = head;
        while (curr != null) {
            System.out.println("B" + curr.order);
            System.out.println("There are " + Math.pow(2, curr.order) + " nodes in this binomial tree");
            System.out.print("The level order traversal of the tree is ");
            printTree(curr);
            curr = curr.sibling;
            System.out.println("\n");
        }
    }
}

public class Main {
    public static void main(String[] args) {
        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));

        System.out.println("Printing Binomial Heap !!!\n");
        heap1.printHeap();

        System.out.println("Extracting Minimum value from the Heap.");
        System.out.println("Minimum key is " + heap1.extractMin().key + "\n");
        System.out.println("Printing Binomial Heap After Extracting Minimum Value!!!\n");
        heap1.printHeap();
    }
}

You can also try this code with Online Java Compiler

Run Code

Python

class BNode:
    def __init__(self, key):
        self.key = key
        self.order = 0
        self.sibling = None
        self.parent = None
        self.child = None

class BHeap:
    def __init__(self, root=None):
        self.head = root
        self.min = None

    def is_empty(self):
        return self.head is None

    def insert(self, root):
        new_heap = BHeap(root)
        self.union_heap(new_heap)

    def combine_heaps(self, heap1, heap2):
        temp1 = BNode(0)
        temp2 = temp1
        root1 = heap1.head
        root2 = heap2.head

        if root1 is None:
            return root2
        if root2 is None:
            return root1

        while root1 or root2:
            if root1 is None:
                temp2.sibling = root2
                temp2 = temp2.sibling
                root2 = root2.sibling
            elif root2 is None:
                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

    def union_heap(self, heap):
        final_heap = BHeap()
        final_heap.head = self.combine_heaps(self, heap)

        if final_heap.head is None:
            self.head = None
            self.min = None
            return

        prev = None
        curr = final_heap.head
        next = curr.sibling

        while next:
            if curr.order != next.order:
                prev = curr
                curr = next
            elif curr.order == next.order and next.sibling and next.sibling.order == curr.order:
                prev = curr
                curr = next
            elif curr.key <= next.key:
                curr.sibling = next.sibling
                self.combine_trees(next, curr)
            else:
                if prev is None:
                    final_heap.head = next
                else:
                    prev.sibling = next
                self.combine_trees(curr, next)
                curr = next

            next = curr.sibling

        self.head = final_heap.head
        self.min = final_heap.head
        curr = self.head

        while curr:
            if curr.key < self.min.key:
                self.min = curr
            curr = curr.sibling

    def combine_trees(self, root1, root2):
        if root1.key < root2.key:
            root1, root2 = root2, root1

        root1.parent = root2
        root1.sibling = root2.child
        root2.child = root1
        root2.order += 1

    def extract_min(self):
        mini = self.first()
        prev = None
        curr1 = self.head

        while curr1 != mini:
            prev = curr1
            curr1 = curr1.sibling

        if prev is None:
            self.head = curr1.sibling
        else:
            prev.sibling = curr1.sibling

        rev_node = None
        curr2 = mini.child
        while curr2:
            next = curr2.sibling
            curr2.sibling = rev_node
            rev_node = curr2
            curr2 = next

        temp = BHeap()
        temp.head = rev_node
        self.union_heap(temp)

        return mini

    def first(self):
        return self.min

    def print_heap(self):
        curr = self.head
        while curr:
            print(f"B{curr.order}")
            print("The level order traversal of the tree is:")
            self.print_tree(curr)
            curr = curr.sibling
            print()

    def print_tree(self, root):
        if root is None:
            return
        queue = [root]

        while queue:
            node = queue.pop(0)
            print(node.key, end=" ")
            if node.child:
                temp = node.child
                while temp:
                    queue.append(temp)
                    temp = temp.sibling

# Usage Example
if __name__ == "__main__":
    heap1 = BHeap()
    heap1.insert(BNode(2))
    heap1.insert(BNode(7))
    heap1.insert(BNode(13))
    heap1.insert(BNode(8))
    heap1.insert(BNode(1))

    print("Printing Binomial Heap!!!")
    heap1.print_heap()

    print("Extracting Minimum value from the Heap.")
    print(f"Minimum key is {heap1.extract_min().key}")
    print("Printing Binomial Heap After Extracting Minimum Value")
    heap1.print_heap()

You can also try this code with Online Python Compiler

Run Code

C#

using System;
using System.Collections.Generic;

class BNode
{
    public int Key, Order;
    public BNode Sibling, Parent, Child;

    public BNode(int key)
    {
        Key = key;
        Order = 0;
        Sibling = Parent = Child = null;
    }
}

class BHeap
{
    public BNode Head, Min;

    public BHeap()
    {
        Head = null;
    }

    public BHeap(BNode root)
    {
        Head = root;
    }

    public bool IsEmpty()
    {
        return Head == null;
    }

    public void Insert(BNode root)
    {
        BHeap newHeap = new BHeap(root);
        UnionHeap(newHeap);
    }

    private BNode CombineHeaps(BHeap heap1, BHeap heap2)
    {
        BNode temp1 = new BNode(0);
        BNode temp2 = temp1;
        BNode root1 = heap1.Head, root2 = heap2.Head;

        if (root1 == null) return root2;
        if (root2 == null) return root1;

        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 void UnionHeap(BHeap heap)
    {
        BHeap finalHeap = new BHeap();
        finalHeap.Head = CombineHeaps(this, heap);

        if (finalHeap.Head == null)
        {
            Head = null;
            Min = null;
            return;
        }

        BNode prev = null, curr = finalHeap.Head, next = curr.Sibling;

        while (next != null)
        {
            if (curr.Order != next.Order)
            {
                prev = curr;
                curr = next;
            }
            else if (curr.Order == next.Order && next.Sibling != null && next.Sibling.Order == curr.Order)
            {
                prev = curr;
                curr = next;
            }
            else if (curr.Key <= next.Key)
            {
                curr.Sibling = next.Sibling;
                CombineTrees(next, curr);
            }
            else
            {
                if (prev == null) finalHeap.Head = next;
                else prev.Sibling = next;
                CombineTrees(curr, next);
                curr = next;
            }
            next = curr.Sibling;
        }

        Head = finalHeap.Head;
        Min = finalHeap.Head;
        curr = Head;

        while (curr != null)
        {
            if (curr.Key < Min.Key) Min = curr;
            curr = curr.Sibling;
        }
    }

    private void CombineTrees(BNode root1, BNode root2)
    {
        if (root1.Key < root2.Key)
        {
            BNode temp = root1;
            root1 = root2;
            root2 = temp;
        }

        root1.Parent = root2;
        root1.Sibling = root2.Child;
        root2.Child = root1;
        root2.Order++;
    }

    public BNode ExtractMin()
    {
        BNode mini = First();
        BNode prev = null, curr1 = Head;

        while (curr1 != mini)
        {
            prev = curr1;
            curr1 = curr1.Sibling;
        }

        if (prev == null) Head = curr1.Sibling;
        else prev.Sibling = curr1.Sibling;

        BNode revNode = null, curr2 = mini.Child;
        while (curr2 != null)
        {
            BNode next = curr2.Sibling;
            curr2.Sibling = revNode;
            revNode = curr2;
            curr2 = next;
        }

        BHeap temp = new BHeap();
        temp.Head = revNode;
        UnionHeap(temp);

        return mini;
    }

    public BNode First()
    {
        return Min;
    }

    public void PrintHeap()
    {
        BNode curr = Head;
        while (curr != null)
        {
            Console.WriteLine($"B{curr.Order}");
            Console.WriteLine("The level order traversal of the tree is:");
            PrintTree(curr);
            curr = curr.Sibling;
            Console.WriteLine();
        }
    }

    private void PrintTree(BNode root)
    {
        if (root == null) return;
        Queue<BNode> queue = new Queue<BNode>();
        queue.Enqueue(root);

        while (queue.Count > 0)
        {
            BNode node = queue.Dequeue();
            Console.Write($"{node.Key} ");
            if (node.Child != null)
            {
                BNode temp = node.Child;
                while (temp != null)
                {
                    queue.Enqueue(temp);
                    temp = temp.Sibling;
                }
            }
        }
        Console.WriteLine();
    }
}

// Usage Example
class Program
{
    static void Main(string[] args)
    {
        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));

        Console.WriteLine("Printing Binomial Heap!!!");
        heap1.PrintHeap();

        Console.WriteLine("Extracting Minimum value from the Heap.");
        Console.WriteLine($"Minimum key is {heap1.ExtractMin().Key}");
        Console.WriteLine("Printing Binomial Heap After Extracting Minimum Value");
        heap1.PrintHeap();
    }
}

JavaScript

class BNode {
  constructor(key) {
    this.key = key;
    this.order = 0;
    this.sibling = null;
    this.parent = null;
    this.child = null;
  }
}

class BHeap {
  constructor(root = null) {
    this.head = root;
    this.min = null;
  }

  isEmpty() {
    return this.head === null;
  }

  insert(root) {
    let newHeap = new BHeap(root);
    this.unionHeap(newHeap);
  }

  combineHeaps(heap1, heap2) {
    let temp1 = new BNode(0);
    let temp2 = temp1;
    let root1 = heap1.head;
    let root2 = heap2.head;

    if (!root1) return root2;
    if (!root2) return root1;

    while (root1 || root2) {
      if (!root1) {
        temp2.sibling = root2;
        temp2 = temp2.sibling;
        root2 = root2.sibling;
      } else if (!root2) {
        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;
  }

  unionHeap(heap) {
    let finalHeap = new BHeap();
    finalHeap.head = this.combineHeaps(this, heap);

    if (!finalHeap.head) {
      this.head = null;
      this.min = null;
      return;
    }

    let prev = null;
    let curr = finalHeap.head;
    let next = curr.sibling;

    while (next) {
      if (curr.order !== next.order) {
        prev = curr;
        curr = next;
      } else if (curr.order === next.order && next.sibling && next.sibling.order === curr.order) {
        prev = curr;
        curr = next;
      } else if (curr.key <= next.key) {
        curr.sibling = next.sibling;
        this.combineTrees(next, curr);
      } else {
        if (!prev) {
          finalHeap.head = next;
        } else {
          prev.sibling = next;
        }
        this.combineTrees(curr, next);
        curr = next;
      }

      next = curr.sibling;
    }

    this.head = finalHeap.head;
    this.min = finalHeap.head;
    curr = this.head;

    while (curr) {
      if (curr.key < this.min.key) {
        this.min = curr;
      }
      curr = curr.sibling;
    }
  }

  combineTrees(root1, root2) {
    if (root1.key < root2.key) {
      [root1, root2] = [root2, root1];
    }

    root1.parent = root2;
    root1.sibling = root2.child;
    root2.child = root1;
    root2.order++;
  }

  extractMin() {
    let mini = this.first();
    let prev = null;
    let curr1 = this.head;

    while (curr1 !== mini) {
      prev = curr1;
      curr1 = curr1.sibling;
    }

    if (!prev) {
      this.head = curr1.sibling;
    } else {
      prev.sibling = curr1.sibling;
    }

    let revNode = null;
    let curr2 = mini.child;
    while (curr2) {
      let next = curr2.sibling;
      curr2.sibling = revNode;
      revNode = curr2;
      curr2 = next;
    }

    let temp = new BHeap();
    temp.head = revNode;
    this.unionHeap(temp);

    return mini;
  }

  first() {
    return this.min;
  }

  printHeap() {
    let curr = this.head;
    while (curr) {
      console.log(`B${curr.order}`);
      console.log("The level order traversal of the tree is:");
      this.printTree(curr);
      curr = curr.sibling;
      console.log();
    }
  }

  printTree(root) {
    if (!root) return;
    let queue = [root];

    while (queue.length > 0) {
      let node = queue.shift();
      process.stdout.write(node.key + " ");
      if (node.child) {
        let temp = node.child;
        while (temp) {
          queue.push(temp);
          temp = temp.sibling;
        }
      }
    }
    console.log();
  }
}

// Usage Example
let 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));

console.log("Printing Binomial Heap!!!");
heap1.printHeap();

console.log("Extracting Minimum value from the Heap.");
console.log(`Minimum key is ${heap1.extractMin().key}`);
console.log("Printing Binomial Heap After Extracting Minimum Value");
heap1.printHeap();

You can also try this code with Online Javascript Compiler

Run Code

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 the main difference between ‘Binomial Heap’ and ‘Binary Heap’?

A Binomial Heap supports faster union operations compared to a Binary Heap, due to its structure of combining binomial trees, making it more suitable for operations involving merging multiple heaps efficiently.

What is the final ‘ Binomial Heap ‘ order if two Binomial Heaps of order ‘K’ are joined?

When two Binomial Heaps of order K are joined, the resulting heap's order becomes K+1, forming a new binomial tree of the next higher order.

What is the number of trees in the Binomial Heap of N nodes?

A Binomial Heap with N nodes has log₂(N) distinct trees, each representing binomial trees of different orders based on the binary representation of N.

How many nodes are there at the depth ‘i’ of a Binomial Tree?

At depth i of a binomial tree with n nodes, there are exactly ⁿCᵢ (n choose i) nodes, representing combinations of nodes at that specific depth level.

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