Open In App

C++ Program to Implement Binomial Heap

Last Updated : 23 Jul, 2025
Suggest changes
Share
Like Article
Like
Report

A binomial heap is a collection of the binomial trees that are linked together. Each binomial tree in the heap has a node structure where the key of a node is greater than or equal to the key of its parent. It is an extension of Binary Heap that allows us to perform union or merge operation faster making them an efficient data structure for implementing priority queues.

In this article, we will learn about the implementation of Binomial Heap in C++, basic operation of binomial heap and its applications.

What is Binomial Tree?

A Binomial Tree Bk​ of order khas the following properties:

  • It is defined recursively:
    • A Binomial Tree of order 0, B0​, is a single node.
    • A Binomial Tree of order k can be constructed by linking two Binomial Trees of order k−1 such that one tree becomes the leftmost child of the other.
  • It has 2^k nodes.
  • It has height k.
  • The root has exactly k children, and each child is the root of a Binomial Tree of order i for 0 <= i <= k-1.

Implementation of Binomial Heap in C++

A binomial heap consists of a set of binomial trees, where each tree follows specific properties:

  • Each binomial tree in a binomial heap obeys the minimum heap property: the key of a parent node is less than or equal to the keys of its children.
  • There can only be either 0 or 1 binomial tree for each order.
  • The degree of a binomial tree is equal to the order of the tree.

Representation of Binomial Heap in C++

Below is a visual representation of the binomial heap with the binomial trees of the orders 0, 1, and 2:

BinomialHeap
Binomial Heap

Here, B0, B1, B2, B3, B4 are the Binomial trees of the different orders in the heap.

To represent a Binomial Heap in C++, we will use a structure to represent the nodes of the binomial tree. To keep the binomial heap generic we have used templates so that it can store multiple data types.

template <typename T>
struct BinomialNode {
 T key;
 int degree;
 BinomialNode<T>* parent;
 BinomialNode<T>* child;
 BinomialNode<T>* sibling;
};

Here,

  • key: represents the value of stored in the node.
  • degree: represent the number of children each node have.
  • parent: is a pointer to the parent node.
  • child: is a pointer to the first child of the node.
  • sibling: is a pointer to the next sibling of the node.

Binomial Heap Operations Implementation in C++

Following are some of the basic operations of binomial heap that are required to manipulate it’s elements:

Operation Name

Description

Time Complexity

Space Complexity

Insert

Inserts a new element into the binomial heap

O(log(n))

O(1)

Extract Minimum

Removes and returns the minimum element

O(log(n))

O(logn)

Merge

Combines two binomial heaps into one

O(log(n))

O(1)

Decrease Key

Decreases the key value of a given node

O(log(n))

O(1)

Delete Node

Deletes a given node from the binomial heap

O(log(n))

O(1)

Insert Implementation in C++

  • Create a Binomial Heap with the new node and treat the new node as a mini Binomial Heap of degree 0.
  • Merge the new Binomial Heap with the existing Binomial Heap by merging them based on their degrees.
  • After merging, ensure that there is at most one tree of each degree in the merged heap by repeatedly combining trees of the same degree to maintain Binomial Heap properties.

Extract Minimum Implementation in C++

  • Traverse through the roots of all trees in the Binomial Heap to find the tree containing the minimum key.
  • Remove this minimum node from its tree and mark the tree’s root for future merging.
  • Merge the child trees of the extracted minimum node's tree with the remaining Binomial Heaps.
  • After merging, ensure that there is at most one tree of each degree in the merged heap by repeatedly combining trees of the same degree to maintain Binomial Heap properties.

Merge Implementation in C++

  • Compare the degrees of the root lists of both heaps and combine them based on their degrees..
  • Add the tree with the smaller degree to the result heap.
  • Move to the next tree in the heap with the smaller degree.
  • Repeat steps 1-3 until one of the heaps is empty.
  • If there are remaining trees in either heap, append them to the result.

Decrease Key Implementation in C++

  • Find the node whose key needs to be decreased.
  • Decrease and update the key of the node.
  • If the decreased key violates the Min-Heap property (parent key is greater than the node's key), swap the node with its parent and continue checking upwards until the Min-Heap property is satisfied.

Delete Node Implementation in C++

  • Decrease the node's key to the minimum possible value (typically negative infinity).
  • Perform the Extract Minimum operation to remove this node from the Binomial Heap.

C++ Program to Implement Binomial Heap

The following program illustrates how we can implement a binomial heap using in C++:

C++ 
// C++ Program to Implement Binomial Heap #include <iostream> #include <limits> #include <vector> using namespace std; // Structure for Binomial Node template <typename T> struct BinomialNode {  T key;  int degree;  BinomialNode<T>* parent;  BinomialNode<T>* child;  BinomialNode<T>* sibling;  // Constructor to initialize a Binomial Node  BinomialNode(T k)  : key(k)  , degree(0)  , parent(nullptr)  , child(nullptr)  , sibling(nullptr)  {  } }; // Class for Binomial Heap template <typename T> class BinomialHeap { private:  BinomialNode<T>*  head; // Pointer to the head of the binomial heap  // Function to merge two binomial trees of the same  // degree  BinomialNode<T>* mergeTrees(BinomialNode<T>* b1,  BinomialNode<T>* b2)  {  // Ensure b1 has the smaller key  if (b1->key > b2->key)  swap(b1, b2);  // Make b1 the parent of b2  b2->parent = b1;  // Link b2 as the first child of b1  b2->sibling = b1->child;  // Update b1's child to b2  b1->child = b2;  // Increase the degree of b1  b1->degree++;  return b1;  }  // Function to consolidate the heap to ensure no two  // binomial trees have the same degree  void consolidate()  {  // Create a vector to store trees by degree  vector<BinomialNode<T>*> trees(64, nullptr);  BinomialNode<T>* current = head;  head = nullptr;  while (current != nullptr) {  // Get the next node  BinomialNode<T>* next = current->sibling;  // Disconnect the current node from its sibling  current->sibling = nullptr;  int degree = current->degree;  while (trees[degree] != nullptr) {  // Merge trees of the same degree  current  = mergeTrees(current, trees[degree]);  trees[degree] = nullptr;  degree++;  }  trees[degree] = current;  current = next;  }  for (BinomialNode<T>* tree : trees) {  if (tree != nullptr) {  tree->sibling = head;  head = tree;  }  }  } public:  BinomialHeap()  : head(nullptr)  {  }  // Function to insert a key into the heap  void insert(T key)  {  BinomialHeap newHeap;  // Create a new heap with a single node  newHeap.head = new BinomialNode<T>(key);  // Merge the new heap into the current heap  merge(newHeap);  }  // Function to Merge another binomial heap into the  // current heap  void merge(BinomialHeap& other)  {  BinomialNode<T>* newHead = nullptr;  BinomialNode<T>** curr = &newHead;  BinomialNode<T>* h1 = head;  BinomialNode<T>* h2 = other.head;  // Merge the root lists of both heaps  while (h1 != nullptr && h2 != nullptr) {  if (h1->degree <= h2->degree) {  *curr = h1;  h1 = h1->sibling;  }  else {  *curr = h2;  h2 = h2->sibling;  }  curr = &((*curr)->sibling);  }  if (h1 != nullptr)  *curr = h1;  if (h2 != nullptr)  *curr = h2;  head = newHead;  // Consolidate the heap to ensure no two trees have  // the same degree  consolidate();  // Clear the other heap  other.head = nullptr;  }  // Function to extract the minimum key from the heap  T extractMin()  {  if (head == nullptr)  throw runtime_error("Heap is empty");  BinomialNode<T>* minNode = head;  BinomialNode<T>* prevMin = nullptr;  BinomialNode<T>* current = head->sibling;  BinomialNode<T>* prev = head;  // Find the minimum key in the root list  while (current != nullptr) {  if (current->key < minNode->key) {  minNode = current;  prevMin = prev;  }  prev = current;  current = current->sibling;  }  // Remove the minimum node from the root list  if (prevMin == nullptr)  head = head->sibling;  else  prevMin->sibling = minNode->sibling;  BinomialHeap newHeap;  BinomialNode<T>* child = minNode->child;  while (child != nullptr) {  BinomialNode<T>* next = child->sibling;  child->parent = nullptr;  child->sibling = newHeap.head;  newHeap.head = child;  child = next;  }  T minKey = minNode->key;  // Delete the minimum node  delete minNode;  // Merge the children of the minimum node back into  // the heap  merge(newHeap);  return minKey;  }  // Function to Decreases the key of a given node  void decreaseKey(BinomialNode<T>* node, T newKey)  {  if (newKey > node->key)  throw runtime_error(  "New key is greater than current key");  node->key = newKey;  BinomialNode<T>* current = node;  BinomialNode<T>* parent = current->parent;  // Bubble up the new key if necessary  while (parent != nullptr  && current->key < parent->key) {  swap(current->key, parent->key);  current = parent;  parent = current->parent;  }  }  // Function to delete a given node from the heap  void deleteNode(BinomialNode<T>* node)  {  decreaseKey(node, numeric_limits<T>::min());  extractMin();  }  // Function to print the binomial heap  void printHeap()  {  BinomialNode<T>* current = head;  while (current != nullptr) {  cout << "B" << current->degree << " ";  printTree(current);  cout << endl;  current = current->sibling;  }  } private:  // Recursively prints a binomial tree  void printTree(BinomialNode<T>* root)  {  cout << root->key << " ";  BinomialNode<T>* child = root->child;  while (child != nullptr) {  printTree(child);  child = child->sibling;  }  } }; int main() {  BinomialHeap<int> heap;  // Insert elements  heap.insert(10);  heap.insert(20);  heap.insert(5);  heap.insert(15);  heap.insert(25);  cout << "Binomial Heap after insertions:" << endl;  heap.printHeap();  // Extract minimum  int min = heap.extractMin();  cout << "\nExtracted minimum: " << min << endl;  cout << "Binomial Heap after extracting minimum:"  << endl;  heap.printHeap();  // Merge with another heap  BinomialHeap<int> otherHeap;  otherHeap.insert(7);  otherHeap.insert(12);  heap.merge(otherHeap);  cout << "\nBinomial Heap after merging:" << endl;  heap.printHeap();  return 0; }

Output
Binomial Heap after insertions: B2 5 10 20 15 B0 25 Extracted minimum: 5 Binomial Heap after extracting minimum: B2 10 15 25 20 Binomial Heap after merging: B2 10 15 25 20 B1 7 12

Applications of Binomial Heap

Following are some of the common applications of a Binomial Heap:

  • The Binomial heaps are often used to the implement priority queues due to their efficient operations for the insertion, deletion and extraction of the minimum element.
  • Use in algorithms like Dijkstra's shortest path and Prim's minimum spanning tree, binomial heaps are used to efficiently manage vertices and edges.
  • In job scheduling systems, binomial heaps can manage a queue of tasks or jobs with the varying priorities. They facilitate efficient insertion and extraction of the tasks based on their priority levels ensuring that higher-priority tasks are executed first.
  • The Binomial heaps are used in the network routing algorithms to the manage routing tables efficiently. They help in the maintaining the shortest path routes or routes with the minimal cost updating them dynamically as the network conditions change.
  • Binomial heaps are also used to implement Huffman coding for data compression.

Related Articles

You can also go through the following articles to improve your understanding about the Binomial Heaps:


S
subramanyasmgm
Article Tags :

Explore

Lightbox