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.

Binomial Heap

Q: 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).

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)

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

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>
using namespace std;

// A Binomial Tree node.
struct Node
{
  int data, degree;
Node *child, *sibling, *parent;
};

Node* newNode(int key)
{
Node *temp = new Node;
temp->data = key;
temp->degree = 0;
temp->child = temp->parent = temp->sibling = NULL;
  return temp;
}

// This function merges two Binomial Trees.
Node* mergeBinomialTrees(Node *bTree1, Node *bTree2)
{

  // Make sure b1 is smaller
  if (bTree1->data > bTree2->data)
swap(bTree1, bTree2);

/*
We make the larger valued tree
a child of smaller valued tree
*/
bTree2->parent = bTree1;
bTree2->sibling = bTree1->child;
bTree1->child = bTree2;
bTree1->degree++;

  return bTree1;
}

/*
This function performs union operation on two.
binomial heap i.e. l1 & l2
*/
list<Node*> unionBionomialHeap(list<Node*> bHeap1, list<Node*> bHeap2)
{

  /* _new to another binomial heap which contain
new heap after merging l1 & l2
*/
list<Node*> newNode;
list<Node*>::iterator it = bHeap1.begin();
list<Node*>::iterator ot = bHeap2.begin();
  while (it!=bHeap1.end() && ot!=bHeap2.end())
{

  // If D(bHeap1) <= D(bHeap2)
  if((*it)->degree <= (*ot)->degree)
{
newNode.push_back(*it);
it++;
}

  // if D(bHeap1) > D(bHeap2)
  else
{
newNode.push_back(*ot);
ot++;
}
}

  /*
If there remain some elements in bHeap1
binomial heap
*/
  while (it != bHeap1.end())
{
newNode.push_back(*it);
it++;
}

  /*
If there remain some elements in bHeap2
binomial heap
*/
  while (ot!=bHeap2.end())
{
newNode.push_back(*ot);
ot++;
}
  return newNode;
}

/*
Adjust function helps in rearranging the heap so that
the heap is in increasing order of degree and
no two binomial trees have a similar degree in this heap
*/
list<Node*> adjust(list<Node*> _heap)
{
  if (_heap.size() <= 1)
  return _heap;
list<Node*> new_heap;
list<Node*>::iterator it1,it2,it3;
it1 = it2 = it3 = _heap.begin();

  if (_heap.size() == 2)
{
it2 = it1;
it2++;
it3 = _heap.end();
}
  else
{
it2++;
it3=it2;
it3++;
}
  while (it1 != _heap.end())
{

  // if only one element remains to be processed
  if (it2 == _heap.end())
it1++;

  /* If D(it1) < D(it2) i.e. merging of the Binomial
Tree pointed by it1 & it2 is not possible
then move next in heap
*/
  else if ((*it1)->degree < (*it2)->degree)
{
it1++;
it2++;
  if(it3!=_heap.end())
it3++;
}

  /*
If D(it1),D(it2) & D(it3) are the same i.e. the
degree of the three consecutive Binomial

            trees are the same in heap
*/
  else if (it3!=_heap.end() &&
(*it1)->degree == (*it2)->degree &&
(*it1)->degree == (*it3)->degree)
{
it1++;
it2++;
it3++;
}

  // If degree of two Binomial Tree are same in heap
  else if ((*it1)->degree == (*it2)->degree)
{
Node *temp;
*it1 = mergeBinomialTrees(*it1,*it2);
it2 = _heap.erase(it2);
  if(it3 != _heap.end())
it3++;
}
}
  return _heap;
}

// Inserting a Binomial Tree into binomial heap
list<Node*> insertATreeInHeap(list<Node*> _heap,
Node *tree)
{

  // Creating a new heap i.e temp
list<Node*> temp;

  // Inserting Binomial Tree into heap
temp.push_back(tree);

  /*
Perform union operation to insert finally
Binomial tree in the original heap
*/
temp = unionBionomialHeap(_heap,temp);

  return adjust(temp);
}

/*
Removing a minimum key element from the binomial heap
this function takes Binomial Tree as input and return
binomial heap after
removing the head of the tree, i.e., the minimum element
*/
list<Node*> removeMinFromTreeReturnBHeap(Node *tree)
{
list<Node*> heap;
Node *temp = tree->child;
Node *lo;

  // Making the binomial heap from the Binomial Tree
  while (temp)
{
lo = temp;
temp = temp->sibling;
lo->sibling = NULL;
heap.push_front(lo);
}
  return heap;
}

// A key is inserted into the binomial heap
list<Node*> insert(list<Node*> _head, int key)
{
Node *temp = newNode(key);
  return insertATreeInHeap(_head,temp);
}

/* Returning the pointer of the minimum value Node
present in the binomial heap
*/
Node* getMin(list<Node*> _heap)
{
list<Node*>::iterator it = _heap.begin();
Node *temp = *it;
  while (it != _heap.end())
{
  if ((*it)->data < temp->data)
temp = *it;
it++;
}
  return temp;
}

list<Node*> extractMin(list<Node*> _heap)
{
list<Node*> new_heap,lo;
Node *temp;

  /* temp contains the pointer of minimum value
element in heap
*/
temp = getMin(_heap);
list<Node*>::iterator it;
it = _heap.begin();
  while (it != _heap.end())
{
  if (*it != temp)
{

  /* Inserting all Binomial Tree into new
binomial heap except the Binomial Tree
contains minimum element
*/
new_heap.push_back(*it);
}
it++;
}
lo = removeMinFromTreeReturnBHeap(temp);
new_heap = unionBionomialHeap(new_heap,lo);
new_heap = adjust(new_heap);
  return new_heap;
}

// Print function for Binomial Tree
void printTree(Node *h)
{
  while (h)
{
cout << h->data << " ";
printTree(h->child);
h = h->sibling;
}
}

// Print function for binomial heap
void printHeap(list<Node*> _heap)
{
list<Node*> ::iterator it;
it = _heap.begin();
  while (it != _heap.end())
{
printTree(*it);
it++;
}
}


// Driver program to test above functions
int main()
{
  int ch,key;
list<Node*> _heap;

  // Insert data in the heap
cout << "Enter the number of elements to add\n";
  int n;

cin >> n;

cout << "Enter the elements\n";

  for(int i=0;i<n;i++){
  int x;
cin >> x;
_heap = insert(_heap,x);
}

cout << "Heap elements after inserting all elements:\n";
printHeap(_heap);

Node *temp = getMin(_heap);
cout << "\nMinimum element of the heap "<< temp->data << "\n";

  // Delete the minimum element of the heap
_heap = extractMin(_heap);
cout << "Heap after deletion of the minimum element\n";
printHeap(_heap);

  return 0;
}

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.