The WP Debugging plugin must have a wp-config.php file that is writable by the filesystem.

Implementation Binomial Heap | Heap | Prepbytes
Heap

Implementation Binomial Heap

Ankit Kochar

In data structures, a binomial heap is similar to a binary heap that also supports the quick merging of two heaps.

What is a Binomial Heap?

A binomial heap is implemented as a set of binomial trees where each binomial tree satisfies the Min Heap property. The min-heap has a property in that each node in the heap has a value lesser than the value of its child nodes. It is an extensive version of the binary heap that supports the quick merging of two heaps.

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 2k nodes.
  2. The depth of the tree is k.
  3. There are always exact kCi 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

This article tried to discuss the Implementation Binomial Heap. Hope this blog helps you understand the concept. To practice problems on Heap feel free to check MYCODE | Competitive Programming – Heaps at Prepbytes

Leave a Reply

Your email address will not be published. Required fields are marked *

Close

Related Post