Binary Heap Is Common, But Ever Heard Of Binomial Heap?

Heap is a popular data structure used in various forms like Min heap and max heap and is mostly used to reduce the time complexity of complex problems. But here we will be discussing a bit different kind of Heap, Binomial Heap.

Binomial Heap

It is a collection of Binomial Trees. A Binomial tree B_k is a tree consisting of two Binomial trees B_k-1 which are linked together. The root of one is the leftmost child of the root of others.

Properties

• Every Binomial Tree (Bk) must have 2k nodes.
• The height of the Binomial tree is k.
• There are (k i) nodes in each level I where, i runs from 0 to k.
• the root has degree k, which is greater than that of any other node; moreover, if the children of the root are numbered from left to right by k − 1, k − 2…, 0, child i is the root of a subtree B_i.

Taking these properties into account, a Binomial Heap is a collection of such trees. This data structures also have some particular properties like-

• The key of a node is greater than or equal to the key of its parent.
• There is at most one tree in the binary heap whose root has a given degree.
• The number of Binomial Trees = number of set bits in the binary form of n, where n is the number of nodes of a Binary Heap.

Supported Methods

• Union (): This operation is used to merge two binomial heaps into one. Most of the heap operations use this method. Suppose we have two Binary Heaps H1, H2, we can call Union(H1, H2) to combine them into a single heap.
• Insert(): This method is used to insert nodes with (H, Key) to our Binomial Heap H. This method then calls the Union() to combine this node with the previous Heap.
• Min(): returns the minimum key in logn time.
• Max(): returns the maximum key in logn time.
• Delete(): removes a key from the heap.
• DecreaseKey(): assigns to node x within heap H the new key-value k, which is assumed to be no greater than its current key value.

Let us see the algorithm for some of these functions separately:

• Union (H1, H2): It basically links the roots of two Binomial Heaps with root H1 and H2, if these are linked either of them can be the new root of the Binomial Tree. Its algorithm can be represented as:

	sibling[H1]=child[H2]
	child[H2]=H1
	degree[H2]++;
	H = HEAP() 
	root[H] = BINOMIAL-HEAP-MERGE(H1, H2)
	free the objects H1 and H2 but not the lists they point to 
	 if root[H] = NIL 
	 then return H 
	 prev-x = NIL 7 x = head[H] 
	 next-x = sibling[x] 
	 while next-x = NIL 
	 do if (degree[x] = degree[next-x]) or (sibling[next-x] = NIL and degree[sibling[next-x]] = degree[x]) 
	then prev-x = x and 2 12 x = next-x and 
	 if key[x] ≤ key[next-x] 14 then sibling[x] = sibling[next-x]
	 BINOMIAL-LINK(next-x, x)
	else if prev-x = NIL
	 then root[H] = next-x 
	 else sibling[prev-x] = next-x 
	BINOMIAL-LINK(x, next-x)
	 x = next-x
	 next-x = sibling[x] 
	 return H
	Insert(): Is used to insert keys into the heap.
	p[x] = NIL 
	 child[x] = NIL 
	 sibling[x] = NIL 
	 degree[x] = 0 
	 head[H ] = x 
	 H = UNION(H, H ) 
	Min(): Is used to get the minimum from the heap
	find the root x with the minimum key in the root list of H, and remove x from the root list of H 
	reverse the order of the linked list of x’s children, and set root[H] to point to the head of the resulting list 
	 H = UNION(H, H ) 
	 return x 

Well, now when we are done with the basic algorithm, lets dig deep in the implementation of it.

Code Implementation:

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

// node data structure
struct Node {
	int data; // contains the key
	int degree; // number of children 
	Node *p; // pointer to parent
	Node *child; // pointer to the leftmost child
	Node *sibling; // pointer to the right sibling
};

typedef Node *Ptr;


// Class that represents Binomial heap data structure
class BinomialHeap {
private:
	// head points to the root of the leftmost binomial tree
	Ptr root;

	// initializes  the node with default values
	// all pointers are initialized to nullptr
	void initializeNode(Ptr node, int data, int deg) {
		node->data = data;
		node->deg = deg;
		node->p = nullptr;
		node->child = nullptr;
		node->sibling = nullptr;
	}

	// merge two binomial trees of same deg
	static void BINOMIAL_LINK(Ptr x, Ptr y) {
		// x must be parent of y
		y->p = x;
		y->sibling = x->child;
		x->child = y;

		// increase the deg of x
		x->deg += 1;
	}

public:
	BinomialHeap() {
		root = nullptr;
	}

	// find the node with mininum data
	Ptr min() {
		// traverse all the roots and find compare
		int min = 999999; //store a max
		Ptr currPtr = root;
		Ptr minPtr = nullptr;

		while (currPtr != nullptr) {
			if (currPtr->data < min) {
				min = currPtr->data;
				minPtr = currPtr;
			}
			currPtr = currPtr->sibling;
		}

		return minPtr;

	}

	// create sample heap (given in figure 5) with three trees for testing
	void createSampleHeap1() {
		// B0
		Ptr node1 = new Node;
		initializeNode(node1, 5, 0);
		root = node1;

		// B1
		Ptr node2 = new Node;
		initializeNode(node2, 17, 1);
		Ptr node3 = new Node;
		initializeNode(node3, 27, 0);
		node2->child = node3;
		node3->p = node2;

		// link B0 and B1
		node1->sibling = node2;

		// B3
		Ptr node4 = new Node;
		initializeNode(node4, 12, 3);
		Ptr node5 = new Node;
		initializeNode(node5, 18, 2);
		Ptr node6 = new Node;
		initializeNode(node6, 16, 1);
		Ptr node7 = new Node;
		initializeNode(node7, 15, 0);
		Ptr node8 = new Node;
		initializeNode(node8, 23, 1);
		Ptr node9 = new Node;
		initializeNode(node9, 30, 0);
		Ptr node10 = new Node;
		initializeNode(node10, 22, 0);
		Ptr node11 = new Node;
		initializeNode(node11, 25, 0);
		node4->child = node5;
		node5->p = node4;
		node6->p = node4;
		node7->p = node4;
		node5->child = node8;
		node5->sibling = node6;
		node6->child = node10;
		node6->sibling = node7;
		node8->p = node5;
		node9->p = node5;
		node10->p = node6;
		node8->child = node11;
		node8->sibling = node9;
		node11->p = node8;

		// link B1 and B3
		node2->sibling = node4;
	}

	// create sample heap (given in figure Fig 10 (a))
	void createSampleHeap2() {
		// B0
		Ptr node1 = new Node;
		initializeNode(node1, 5, 0);
		root = node1;

		// B2
		Ptr node2 = new Node;
		initializeNode(node2, 6, 2);
		Ptr node3 = new Node;
		initializeNode(node3, 12, 1);
		Ptr node4 = new Node;
		initializeNode(node4, 34, 0);
		Ptr node5 = new Node;
		initializeNode(node5, 33, 0);
		node2->child = node3;
		node3->p = node2;
		node4->p = node2;
		node3->child = node5;
		node3->sibling = node4;
		node5->p = node3;

		// link B0 and B1
		node1->sibling = node2;

		// B3
		Ptr node6 = new Node;
		initializeNode(node6, 1, 3);
		Ptr node7 = new Node;
		initializeNode(node7, 2, 2);
		Ptr node8 = new Node;
		initializeNode(node8, 12, 1);
		Ptr node9 = new Node;
		initializeNode(node9, 6, 0);
		Ptr node10 = new Node;
		initializeNode(node10, 4, 1);
		Ptr node11 = new Node;
		initializeNode(node11, 13, 0);
		Ptr node12 = new Node;
		initializeNode(node12, 18, 0);
		Ptr node13 = new Node;
		initializeNode(node13, 7, 0);
		node6->child = node7;
		node7->p = node6;
		node8->p = node6;
		node7->p = node6;
		node7->child = node10;
		node7->sibling = node8;
		node8->child = node12;
		node8->sibling = node9;
		node10->p = node7;
		node11->p = node7;
		node12->p = node8;
		node10->child = node13;
		node10->sibling = node11;
		node13->p = node10;

		// link B1 and B3
		node2->sibling = node6;
	}

	// create sample heap 
	void createSampleHeap3() {
		// B1
		Ptr node1 = new Node;
		initializeNode(node1, 29, 1);
		Ptr node2 = new Node;
		initializeNode(node2, 33, 0);
		node1->child = node2;
		node2->p = node1;
		root = node1;

		// B2
		Ptr node3 = new Node;
		initializeNode(node3, 21, 2);
		Ptr node4 = new Node;
		initializeNode(node4, 23, 1);
		Ptr node5 = new Node;
		initializeNode(node5, 78, 0);
		Ptr node6 = new Node;
		initializeNode(node6, 50, 0);
		node3->child = node4;
		node4->p = node3;
		node5->p = node3;
		node4->child = node6;
		node4->sibling = node5;
		node6->p = node4;

		// link B1 and B2
		node1->sibling = node3;

	}

	// insert a node to the heap
	void insert(int data) {
		BinomialHeap h;
		Ptr node = new Node;
		initializeNode(node, data, 0);
		h.setRoot(node);
		merge(h);
	}

	// returns the root pointer
	Ptr getRoot() {
		return root;
	}

	// setter for root
	void setRoot(Ptr root) {
		this->root = root;
	}

	// merge two binomial heaps H and H'
	// resulting heap will be H
	void merge(BinomialHeap h1) {
		Ptr curr1 = getRoot();
		Ptr curr2 = h1.getRoot();
		Ptr curr3 = nullptr;
		Ptr temp = nullptr;

		if (curr1->deg <= curr2->deg) {
			curr3 = curr1;
			curr1 = curr1->sibling;
		} else {
			curr3 = curr2;
			curr2 = curr2->sibling;
		}

		temp = curr3;

		// merge two heaps without taking care of trees with same deg
		// the roots of the tree must be in accending order of deg from
		// left to right
		while(curr1 != nullptr && curr2 != nullptr) {
			if (curr1->deg <= curr2->deg) {
				curr3->sibling = curr1;
				curr1 = curr1->sibling;
			} else {
				curr3->sibling = curr2;
				curr2 = curr2->sibling;
			}

			curr3 = curr3->sibling;
		}

		if (curr1 != nullptr) {
			// copy all the remaining trees of heap1
			while(curr1 != nullptr) {
				curr3->sibling = curr1;
				curr1 = curr1->sibling;
				curr3 = curr3->sibling;
			}
		}

		if (curr2 != nullptr) {
			// copy all the remaining trees of heap2
			while(curr2 != nullptr) {
				curr3->sibling = curr2;
				curr2 = curr2->sibling;
				curr3 = curr3->sibling;
			}
		}


		// scan the merged list and repeatidly merge binomial trees with same deg
		curr3 = temp;
		Ptr prev = nullptr;
		Ptr next = curr3->sibling;

		while (next != nullptr) {
			// if two adjacent tree roots have different deg or 3 consecutive roots have same deg
			// move to the next tree
			if ((curr3->deg != next->deg )|| (next->sibling != nullptr && curr3->deg == next->sibling->deg)) {
				prev = curr3;
				curr3 = next;
			} else {
				// otherwise repeatdly merge binomial trees with same deg
				if (curr3->data <= next->data) {
					curr3->sibling = next->sibling;
					BinomialHeap::BINOMIAL_LINK(curr3, next);
				} else {
					if (prev == nullptr) {
						temp = next;
					} else {
						prev->sibling = next;
					}

					BinomialHeap::BINOMIAL_LINK(next, curr3);
					curr3 = next;
				}
			}

			next = curr3->sibling;
		}

		setRoot(temp);
	}

	// deletes the smallest node from the heap
	Ptr deleteMin() {
		Ptr curr = root;
		Ptr prevMin = nullptr;
		// find the root with minimum key
		Ptr minPtr = nullptr;
		Ptr prevPtr = nullptr;
		int min = 999999;

		while (curr != nullptr) {
			if (curr->data <= min) {
				min = curr->data;
				prevMin = prevPtr;
				minPtr = curr;
			}
			prevPtr = curr;
			curr = curr->sibling;
		}

		// delete the node pointed by minPtr
		if (prevMin != nullptr && minPtr->sibling != nullptr) {
			prevMin->sibling = minPtr->sibling;
		} else if (prevMin != nullptr && minPtr->sibling == nullptr) {
			prevMin->sibling = nullptr;
		}else if(prevMin == nullptr and minPtr->sibling != nullptr) {
		        root = minPtr->sibling;
		}else if(prevMin == nullptr and minPtr->sibling == nullptr) {
		        root = nullptr;
		}

		// remove parent reference from all its child
		Ptr childPtr = minPtr->child;
		while (childPtr != nullptr) {
			childPtr->p = nullptr;
			childPtr = childPtr->sibling;
		}

		// reverse the order 
		stack<Ptr> s;
		childPtr = minPtr->child;
		while (childPtr != nullptr) {
			s.push(childPtr);
			childPtr = childPtr->sibling;
		}

		curr = s.top();
		Ptr temp = curr;
		s.pop();

		while (!s.empty()) {
			curr->sibling = s.top();
			s.pop();
			curr = curr->sibling;
		}

		curr->sibling = nullptr;

		BinomialHeap h;
		h.setRoot(temp);

		// merge 
		merge(h);

		// return the min root
		return minPtr;
	}
};

int main() {
	BinomialHeap heap1;
	BinomialHeap heap2;
	BinomialHeap heap3;
	heap1.createSampleHeap2();
	heap2.createSampleHeap3();
	heap1.merge(heap2);
	heap1.printHeap();
	heap1.deleteMin();
	heap1.printHeap();
	return 0;
}

Time Complexities

Frequently Asked Questions

Hope this article has cleared a lot of doubts about Binomial Heap and also as an introduction to this data structure. It might help programmers and developers. Keep following Coding Ninjas for more such interesting blogs.

By Aniruddha Guin