Implementation Binomial Heap

Last Updated on July 24, 2023 by Mayank Dham

The binomial heap in data structure stands as a true marvel, combining the elegance of binary trees with the efficiency of heap-based operations. Born from the ingenuity of computer scientists Peter Bayer and Michael Dietz in 1978, the binomial heap has since become a fundamental building block in various algorithmic applications. Its ability to support rapid insertion, deletion, and merging operations has made it a go-to choice for optimizing complex data manipulation tasks.

In this article, we embark on a journey into the world of the binomial heap – a versatile, self-balancing data structure. We dive deep into its foundational principles, exploring how the structure leverages the power of binomial trees to perform efficiently even with large datasets. Unraveling its inner workings, we uncover the mechanics of merging and consolidating binomial trees, which form the crux of its efficiency.

What is a Binomial Heap in data structure?

A binomial heap is a specialized tree-based data structure in computer science and a type of heap data structure. The min-heap has a property in that each node in the heap has a value lesser than the value of its child nodes. Binomial heaps are designed to efficiently support various operations, making them a powerful tool in algorithm design and data manipulation tasks. At its core, a binomial heap is a collection of binomial trees, which are defined as a set of binary trees obeying specific rules. A binomial tree of order k is a rooted tree with the following properties:

• The tree has k nodes.
• The root node has a degree of k (i.e., k child nodes).
• Each child node is the root of a binomial tree of order k-1, k-2, and so on, down to a binomial tree of order 0 (which is just a single node).

Let’s see, binomial heap example:-

What is a Binomial Tree?

A binomial tree of order 0 has a single node. A binomial tree of order k can be made by taking two binomial trees of order k-1 and making one of them as the leftmost child of the other.
A Binomial Tree of order k has the properties which are listed below:

1. A binomial tree always has exactly 2^k nodes.
2. The depth of the tree is k.
3. There are always exact ^kC_i nodes at depth i for i = 0, 1, . . . , k.
4. The root having degree k and children of that root are themselves Binomial Trees with order k-1, k-2,.. 0 from left to right.

Binomial Heaps and Binary representation of a number:

A binomial heap that has n nodes consists of the binomial trees equal to the number of 1 bit in the binary representation of n.
For better understanding let’s look into an example, suppose a binomial heap with 9 nodes is to be created. 1001 will be the binary representation of 9. In the binary representation of 9, digit 1 occurs at 0 and 3 positions, so the binomial heap will contain the binomial trees of 0 and 3 degrees.

Functions of Binomial Heap:

The central function in Binomial Heap is the union(), all other functions mainly use this function. The union() operation is used to merge two Binomial Heaps into one. Let us first discuss other functions, we will discuss union later.

insert(H, k): In this function, a key ‘k’ is inserted to Binomial Heap ‘H’. This function firstly creates a Binomial Heap with one key ‘k’, then calls union on binomial heap ‘H’ and the new Binomial heap.

getMin(H): This function is used to get the minimum key from the binomial heap. To getMin() is to iterate over the list of roots of Binomial Trees and return the smallest key. O(Logn) will be the time complexity of this function. we can optimize this function to O(1) by maintaining a pointer that will always point to the minimum key root.

extractMin(H): This function uses union() function. Firstly, we call getMin() to find the minimum key of the Binomial Tree, then we will delete that node and create a new Binomial Heap by connecting all subtrees of the removed minimum node. At last, we will call the union() function on the binomial heap ‘H’ and the newly created Binomial Heap. O(Logn) will be the time complexity.

Union function in Binomial Heap:

Two Binomial Heaps H1 and H2 are given, the union(H1, H2) function will create a single Binomial Heap.

Initially merge the two Heaps in non-decreasing order of degrees. In the following diagram, figure(b) shows the result after merging.
After the merging, we have to check that there must be at most one Binomial Tree of any order. If there is more than one binomial tree then we need to combine Binomial Trees of the same order. We traverse the list of merged roots, we keep track of three-pointers, prev, x, and next-x. The following 4 cases might arise when we traverse the list of roots.

• Case 1: If Orders of x and next-x are not the same, we will move ahead.

• In the next 3 cases, the orders of x and next-x are the same.

• Case 2: If the order of next-next-x is also the same, simply move ahead.

• Case 3: If the key of x is smaller than or equal to the key of next-x, then make next-x as a child of x.

• Case 4: If the key of x is greater than the key of next-x, then make x as the child of next by linking it with next.

Code Implementation

#include<bits/stdc++.h>
using namespace std;

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

Node* mergeBinomialTrees(Node *b1, Node *b2)
{
	if (b1->data > b2->data)
		swap(b1, b2);

	b2->parent = b1;
	b2->sibling = b1->child;
	b1->child = b2;
	b1->degree++;

	return b1;
}

list<Node*> unionBionomialHeap(list<Node*> l1,
							list<Node*> l2)
{
	list<Node*> _new;
	list<Node*>::iterator it = l1.begin();
	list<Node*>::iterator ot = l2.begin();
	while (it!=l1.end() && ot!=l2.end())
	{
		if((*it)->degree <= (*ot)->degree)
		{
			_new.push_back(*it);
			it++;
		}
		else
		{
			_new.push_back(*ot);
			ot++;
		}
	}

	while (it != l1.end())
	{
		_new.push_back(*it);
		it++;
	}

	while (ot!=l2.end())
	{
		_new.push_back(*ot);
		ot++;
	}
	return _new;
}

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 (it2 == _heap.end())
			it1++;

		else if ((*it1)->degree < (*it2)->degree)
		{
			it1++;
			it2++;
			if(it3!=_heap.end())
				it3++;
		}

		else if (it3!=_heap.end() &&
				(*it1)->degree == (*it2)->degree &&
				(*it1)->degree == (*it3)->degree)
		{
			it1++;
			it2++;
			it3++;
		}

		else if ((*it1)->degree == (*it2)->degree)
		{
			Node *temp;
			*it1 = mergeBinomialTrees(*it1,*it2);
			it2 = _heap.erase(it2);
			if(it3 != _heap.end())
				it3++;
		}
	}
	return _heap;
}

list<Node*> insertATreeInHeap(list<Node*> _heap,
							Node *tree)
{
	list<Node*> temp;

	temp.push_back(tree);

	temp = unionBionomialHeap(_heap,temp);

	return adjust(temp);
}


list<Node*> removeMinFromTreeReturnBHeap(Node *tree)
{
	list<Node*> heap;
	Node *temp = tree->child;
	Node *lo;

	while (temp)
	{
		lo = temp;
		temp = temp->sibling;
		lo->sibling = NULL;
		heap.push_front(lo);
	}
	return heap;
}

list<Node*> insert(list<Node*> _head, int key)
{
	Node *temp = newNode(key);
	return insertATreeInHeap(_head,temp);
}

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 = getMin(_heap);
	list<Node*>::iterator it;
	it = _heap.begin();
	while (it != _heap.end())
	{
		if (*it != temp)
		{
			new_heap.push_back(*it);
		}
		it++;
	}
	lo = removeMinFromTreeReturnBHeap(temp);
	new_heap = unionBionomialHeap(new_heap,lo);
	new_heap = adjust(new_heap);
	return new_heap;
}

void printTree(Node *h)
{
	while (h)
	{
		cout << h->data << " ";
		printTree(h->child);
		h = h->sibling;
	}
}

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


int main()
{
	int ch,key;
	list<Node*> _heap;

	_heap = insert(_heap,20);
	_heap = insert(_heap,40);
	_heap = insert(_heap,60);

	cout << "Heap after insertion:\n";
	printHeap(_heap);

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

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

	return 0;
}

Output:

Heap after insertion:
60 20 40
Minimum element of Heap 20
Heap after deletion of minimum element
40 60

Time Complexity for different operations in binomial heap in data structures:

• Insertion: O(log N)
  Inserting a new element into a binomial heap requires creating a new binomial tree of order 0 and then merging it with the existing heap. The merging process involves merging binomial trees of the same order until no two trees of the same order remain. This process takes O(log N) time, where N is the number of elements in the binomial heap.

• Deletion (Extract-Min or Extract-Max): O(log N)
  Removing the minimum (or maximum) element from a binomial heap involves consolidating the remaining binomial trees. The consolidation process combines binomial trees of different orders to ensure that no two trees of the same order exist in the heap. This process takes O(log N) time, where N is the number of elements in the binomial heap.

• Merge: O(log N)
  Merging two binomial heaps involves combining the binomial trees in both heaps to form a new binomial heap. The merging process is similar to the consolidation process in deletion and takes O(log N) time, where N is the total number of elements in both heaps.

• Decrease-Key (or Increase-Key): O(log N)
  Modifying the value of a node in the binomial heap and maintaining the heap properties requires performing a series of cascading link operations, where a node may move up the tree to maintain the heap order. The cascading link operations take O(log N) time, where N is the number of elements in the heap.

Space Complexity of Binomial Heap in data structures:

The space complexity of a binomial heap in data structures is O(N), where N is the number of elements in the heap. Each element in the heap is represented by a node in a binomial tree, and the total number of nodes in all the binomial trees gives the space complexity. Additionally, the merging and consolidation processes may require temporary space proportional to the height of the heap, which is O(log N) at most. Therefore, the overall space complexity of a binomial heap is O(N).

Conclusion
In conclusion, the binomial heap stands as a testament to the power of efficient data manipulation in the realm of data structures. Throughout this article, we have delved into the intricacies of binomial heaps, uncovering their unique properties, operations, and applications. With its ability to maintain logarithmic time complexity for key operations like insertion, deletion, and merging, the binomial heap proves to be a versatile and powerful tool in algorithm design.

We began our exploration by understanding the fundamental concept of binomial trees and how they form the building blocks of binomial heaps. The elegant properties of binomial trees, coupled with the heap-based structure, enable efficient data management and priority-based operations.

FAQ on binomial Heap in Data Structures:

Here are some FAQs related to binomial heap in data structures.

Q1. Can binomial heaps handle duplicate elements efficiently?
Yes, binomial heaps can efficiently handle duplicate elements. The heap properties and merging process ensure that duplicate elements are preserved and sorted correctly within the heap.

Q2. What is the advantage of using a binomial heap over other heap data structures?
Binomial heaps offer several advantages over other heap data structures. Their logarithmic time complexity for key operations such as insertion, deletion, and merging ensures efficient data manipulation. Additionally, the merging operation in binomial heaps is particularly efficient, making it ideal for applications that require frequent merging of heaps.

Q3. Is it possible to implement a priority queue using a binomial heap?
Yes, binomial heaps are commonly used to implement priority queues due to their efficient operations and self-balancing nature. They are particularly useful in graph algorithms like Dijkstra’s algorithm and Prim’s algorithm.

Q4. Can binomial heaps handle dynamic data sets efficiently?
Yes, binomial heaps are well-suited for handling dynamic data sets efficiently. They allow for dynamic insertions, deletions, and changes to key values while maintaining logarithmic time complexity for these operations.

Q5. How does a binomial heap compare to a binary heap?
Binomial heaps and binary heaps are both types of heap data structures. While binary heaps are simpler and more straightforward to implement, binomial heaps offer superior merging operations, making them more efficient when merging multiple heaps.

Q6. Is it possible to decrease or increase the key of an element in a binomial heap?
Yes, binomial heaps support the decrease-key (or increase-key) operation, which allows modifying the value of an element and maintaining the heap properties efficiently.