A binomial Heap is a collection of Binomial Trees. A binomial tree Bk is an ordered tree defined recursively. A binomial Tree B0 consists of a single node.
A binomial tree is an ordered tree defined recursively. A binomial tree Bk consists of two binomial trees Bk-1 that are linked together. The root of one is the leftmost child of the root of the other.
Binomial trees are defined recursively. A binomial tree Bk is defined as follows
- B0 is a single node.
- Bk is formed by linking two binomial trees Bk-1 such that the root of one is the leftmost child of the root of the other.
Some properties of binomial trees are
- Binomial tree with Bk has 2k nodes.
- Height of the tree is k
- There are exactly j! / (i! * (j-i)!) nodes at depth i for all i in range 0 to k.
What is Binomial Heap?
As mentioned above, a binomial heap is a collection of binomial trees. These binomial trees are linked together in a specific way. The binomial heap has the following properties
- Each binomial tree in the heap follows the min-heap property.
- No two binomial trees in the heap can have the same number of nodes.
- There is at most one binomial tree of any order.
Representation of Binomial Heap
Following is a representation of binomial heap, where Bk is a binomial heap of order k.
Some binomial heaps are like below
Example of Binomial Heap
This binomial Heap H consists of binomial trees B0, B2 and B3. Which have 1, 4 and 8 nodes respectively. And in total n = 13 nodes. The root of binomial trees are linked by a linked list in order of increasing degree
Operations on Binomial Heap
Following are the operations that can be performed on a binomial heap
- Insert: As name suggests, it is used to insert a node into the heap.
- Union: It is used to merge two binomial heaps into a single binomial heap.
- Extract-Min: This operation removes the node with the smallest key from the heap.
- Decrease-Key: This operation decreases the key of a node in the heap.
- Delete: Simply put, it deletes a node from the heap.
Implementation of Binomial Heap
We can implement a binomial heap using a linked list of binomial trees. Each node in the linked list is a binomial tree. The root of each binomial tree is the head of the linked list. The linked list is ordered by the order of the binomial trees. The binomial heap is the head of the linked list.
Implementation of binomial heap using following steps
1. Create a new node with the given key. 2. Merge the new node with the binomial heap. 3. Adjust the binomial heap to maintain the heap property. 4. Insert the new node into the binomial heap. 5. Print the binomial heap.
Code for Binomial Heap
Following is the implementation of binomial heap in C, C++, Java and Python.
In the following code, first we create a structure Node to represent a node in the binomial heap. The structure contains the data, degree, child, sibling, and parent of the node. We then define functions to create a new node, merge two binomial trees, union two binomial heaps, adjust the heap, and insert a new node into the heap. Finally, we print the binomial heap.
#include <stdio.h>#include <stdlib.h>#include <limits.h>structNode{int data, degree;structNode*child,*sibling,*parent;};structNode*newNode(int key){structNode*temp =(structNode*)malloc(sizeof(structNode));
temp->data = key;
temp->degree =0;
temp->child = temp->parent = temp->sibling =NULL;return temp;}structNode*mergeBinomialTrees(structNode*b1,structNode*b2){if(b1->data > b2->data){structNode*temp = b1;
b1 = b2;
b2 = temp;}
b2->parent = b1;
b2->sibling = b1->child;
b1->child = b2;
b1->degree++;return b1;}structNode*unionBinomialHeap(structNode*h1,structNode*h2){if(!h1)return h2;if(!h2)return h1;structNode*newHeap =NULL,**pos =&newHeap;structNode*curr1 = h1,*curr2 = h2;while(curr1 && curr2){if(curr1->degree <= curr2->degree){*pos = curr1;
curr1 = curr1->sibling;}else{*pos = curr2;
curr2 = curr2->sibling;}
pos =&((*pos)->sibling);}*pos =(curr1)? curr1 : curr2;return newHeap;}structNode*adjustHeap(structNode*head){if(!head)returnNULL;structNode*prev =NULL,*curr = head,*next = head->sibling;while(next){if(curr->degree != next->degree ||(next->sibling && next->sibling->degree == curr->degree)){
prev = curr;
curr = next;}else{if(curr->data <= next->data){
curr->sibling = next->sibling;
curr =mergeBinomialTrees(curr, next);}else{if(!prev) head = next;else prev->sibling = next;
curr =mergeBinomialTrees(next, curr);}}
next = curr->sibling;}return head;}structNode*insert(structNode*heap,int key){structNode*temp =newNode(key);returnadjustHeap(unionBinomialHeap(heap, temp));}voidprintTree(structNode*h){while(h){printf("%d ", h->data);printTree(h->child);
h = h->sibling;}}voidprintHeap(structNode*h){printf("Binomial Heap: \n");while(h){printf("B%d: ", h->degree);printTree(h);printf("\n");
h = h->sibling;}}intmain(){structNode*hp =NULL;
hp =insert(hp,10);
hp =insert(hp,20);
hp =insert(hp,30);
hp =insert(hp,40);printHeap(hp);return0;}
Output
Following is the output of the above C code
10 20 30 40
Extract-Min Operation in Binomial Heap
The extract-min operation removes the node with the smallest key from the binomial heap. The extract-min operation is performed as follows
1. Find the node with the smallest key in the binomial heap. 2. Remove the node from the binomial heap. 3. Now, Let's Merge the children of the node with the binomial heap. 4. Adjust the binomial heap to maintain the heap property. 5. Return the new binomial heap.
Code for Extract-Min Operation
Following is the implementation of extract-min operation in C, C++, Java and Python.
#include <stdio.h>#include <stdlib.h>#include <limits.h>structNode{int data, degree;structNode*child,*sibling,*parent;};structNode*newNode(int key){structNode*temp =(structNode*)malloc(sizeof(structNode));
temp->data = key;
temp->degree =0;
temp->child = temp->parent = temp->sibling =NULL;return temp;}structNode*mergeBinomialTrees(structNode*b1,structNode*b2){if(b1->data > b2->data){structNode*temp = b1;
b1 = b2;
b2 = temp;}
b2->parent = b1;
b2->sibling = b1->child;
b1->child = b2;
b1->degree++;return b1;}structNode*unionBinomialHeap(structNode*h1,structNode*h2){if(!h1)return h2;if(!h2)return h1;structNode*newHeap =NULL,**pos =&newHeap;structNode*curr1 = h1,*curr2 = h2;while(curr1 && curr2){if(curr1->degree <= curr2->degree){*pos = curr1;
curr1 = curr1->sibling;}else{*pos = curr2;
curr2 = curr2->sibling;}
pos =&((*pos)->sibling);}*pos =(curr1)? curr1 : curr2;return newHeap;}structNode*adjustHeap(structNode*head){if(!head)returnNULL;structNode*prev =NULL,*curr = head,*next = head->sibling;while(next){if(curr->degree != next->degree ||(next->sibling && next->sibling->degree == curr->degree)){
prev = curr;
curr = next;}else{if(curr->data <= next->data){
curr->sibling = next->sibling;
curr =mergeBinomialTrees(curr, next);}else{if(!prev) head = next;else prev->sibling = next;
curr =mergeBinomialTrees(next, curr);}}
next = curr->sibling;}return head;}structNode*insert(structNode*heap,int key){structNode*temp =newNode(key);returnadjustHeap(unionBinomialHeap(heap, temp));}structNode*getMin(structNode*heap){if(!heap)returnNULL;structNode*min = heap;structNode*curr = heap->sibling;while(curr){if(curr->data < min->data) min = curr;
curr = curr->sibling;}return min;}structNode*extractMin(structNode*heap){if(!heap)returnNULL;structNode*min =getMin(heap);structNode*prev =NULL,*curr = heap;while(curr != min){
prev = curr;
curr = curr->sibling;}if(prev) prev->sibling = min->sibling;else heap = min->sibling;structNode*child = min->child;structNode*newHeap =NULL;while(child){structNode*next = child->sibling;
child->sibling = newHeap;
child->parent =NULL;
newHeap = child;
child = next;}
newHeap =adjustHeap(newHeap);return newHeap;}voidprintTree(structNode*h){while(h){printf("%d ", h->data);printTree(h->child);
h = h->sibling;}}voidprintHeap(structNode*h){printf("Binomial Heap: \n");while(h){printf("B%d: ", h->degree);printTree(h);printf("\n");
h = h->sibling;}}intmain(){structNode*hp =NULL;
hp =insert(hp,10);
hp =insert(hp,20);
hp =insert(hp,30);
hp =insert(hp,40);printHeap(hp);structNode*min =getMin(hp);printf("Min: %d\n", min->data);
hp =extractMin(hp);printHeap(hp);return0;}
Output
Following is the output of the above C code
Binomial Heap: B0: 10 B1: 20 B2: 30 B3: 40 Min: 10 Binomial Heap: B1: 20 B2: 30 B3: 40
Decrease-Key Operation in Binomial Heap
Decrease-key is a important operation in the binomial heap. It is used to decrease the value of a key in the binomial heap. The decrease-key operation is performed as follows
Algorithm for Decrease-Key Operation
Follow the steps below to decrease-key.
1. Decrease the value of the key to a new value. 2. If the new value is greater than the parent of the node, then return. 3. If the new value is less than the parent of the node, then swap the values of the node and its parent. 4. Repeat the above step until the node reaches the root or the parent of the node is less than the node.
Code for Decrease-Key Operation in Binomial Heap
Following is the implementation of decrease-key operation in C, C++, Java and Python.
#include <stdio.h>#include <stdlib.h>#include <limits.h>structNode{int data, degree;structNode*child,*sibling,*parent;};structNode*newNode(int key){structNode*temp =(structNode*)malloc(sizeof(structNode));
temp->data = key;
temp->degree =0;
temp->child = temp->parent = temp->sibling =NULL;return temp;}structNode*mergeBinomialTrees(structNode*b1,structNode*b2){if(b1->data > b2->data){structNode*temp = b1;
b1 = b2;
b2 = temp;}
b2->parent = b1;
b2->sibling = b1->child;
b1->child = b2;
b1->degree++;return b1;}structNode*unionBinomialHeap(structNode*h1,structNode*h2){if(!h1)return h2;if(!h2)return h1;structNode*newHeap =NULL,**pos =&newHeap;structNode*curr1 = h1,*curr2 = h2;while(curr1 && curr2){if(curr1->degree <= curr2->degree){*pos = curr1;
curr1 = curr1->sibling;}else{*pos = curr2;
curr2 = curr2->sibling;}
pos =&((*pos)->sibling);}*pos =(curr1)? curr1 : curr2;return newHeap;}structNode*adjustHeap(structNode*head){if(!head)returnNULL;structNode*prev =NULL,*curr = head,*next = head->sibling;while(next){if(curr->degree != next->degree ||(next->sibling && next->sibling->degree == curr->degree)){
prev = curr;
curr = next;}else{if(curr->data <= next->data){
curr->sibling = next->sibling;
curr =mergeBinomialTrees(curr, next);}else{if(!prev) head = next;else prev->sibling = next;
curr =mergeBinomialTrees(next, curr);}}
next = curr->sibling;}return head;}structNode*insert(structNode*heap,int key){structNode*temp =newNode(key);returnadjustHeap(unionBinomialHeap(heap, temp));}structNode*getMin(structNode*heap){if(!heap)returnNULL;structNode*min = heap;structNode*curr = heap->sibling;while(curr){if(curr->data < min->data) min = curr;
curr = curr->sibling;}return min;}structNode*extractMin(structNode*heap){if(!heap)returnNULL;structNode*min =getMin(heap);structNode*prev =NULL,*curr = heap;while(curr != min){
prev = curr;
curr = curr->sibling;}if(prev) prev->sibling = min->sibling;else heap = min->sibling;structNode*child = min->child;structNode*newHeap =NULL;while(child){structNode*next = child->sibling;
child->sibling = newHeap;
child->parent =NULL;
newHeap = child;
child = next;}
newHeap =adjustHeap(newHeap);return newHeap;}voiddecreaseKey(structNode*heap,structNode*node,int key){if(!heap ||!node)return;if(key > node->data)return;
node->data = key;structNode*parent = node->parent;while(parent && node->data < parent->data){int temp = node->data;
node->data = parent->data;
parent->data = temp;
node = parent;
parent = node->parent;}}voidprintTree(structNode*h){while(h){printf("%d ", h->data);printTree(h->child);
h = h->sibling;}}voidprintHeap(structNode*h){while(h){printf("B%d: ", h->degree);printTree(h);printf("\n");
h = h->sibling;}}intmain(){structNode*hp =NULL;
hp =insert(hp,10);
hp =insert(hp,20);
hp =insert(hp,30);
hp =insert(hp,40);printf("Binomial Heap: \n");printHeap(hp);structNode*min =getMin(hp);printf("Min: %d\n", min->data);decreaseKey(hp, hp->sibling,5);printf("Binomial Heap after Decrease-Key operation\n");printHeap(hp);return0;}
Output
Following is the output of the above C code
Binomial Heap: B2: 10 30 40 20 Min: 10 Binomial Heap after Decrease-Key operation B2: 10 30 40 20
Delete Operation in Binomial Heap
Delete operation is used for deleting a key from a binomial heap.
Algorithm for Delete Operation
1. Decrease the key value to minus infinity. 2. Now extract the minimum value from the heap.
Code for Delete Operation in Binomial Heap
Following is the implementation of delete operation in C, C++, Java and Python.
#include <stdio.h>#include <stdlib.h>#include <limits.h>structNode{int data, degree;structNode*child,*sibling,*parent;};structNode*newNode(int key){structNode*temp =(structNode*)malloc(sizeof(structNode));
temp->data = key;
temp->degree =0;
temp->child = temp->parent = temp->sibling =NULL;return temp;}structNode*mergeBinomialTrees(structNode*b1,structNode*b2){if(b1->data > b2->data){structNode*temp = b1;
b1 = b2;
b2 = temp;}
b2->parent = b1;
b2->sibling = b1->child;
b1->child = b2;
b1->degree++;return b1;}structNode*unionBinomialHeap(structNode*h1,structNode*h2){if(!h1)return h2;if(!h2)return h1;structNode*newHeap =NULL,**pos =&newHeap;structNode*curr1 = h1,*curr2 = h2;while(curr1 && curr2){if(curr1->degree <= curr2->degree){*pos = curr1;
curr1 = curr1->sibling;}else{*pos = curr2;
curr2 = curr2->sibling;}
pos =&((*pos)->sibling);}*pos =(curr1)? curr1 : curr2;return newHeap;}structNode*adjustHeap(structNode*head){if(!head)returnNULL;structNode*prev =NULL,*curr = head,*next = head->sibling;while(next){if(curr->degree != next->degree ||(next->sibling && next->sibling->degree == curr->degree)){
prev = curr;
curr = next;}else{if(curr->data <= next->data){
curr->sibling = next->sibling;
curr =mergeBinomialTrees(curr, next);}else{if(!prev) head = next;else prev->sibling = next;
curr =mergeBinomialTrees(next, curr);}}
next = curr->sibling;}return head;}structNode*insert(structNode*heap,int key){structNode*temp =newNode(key);returnadjustHeap(unionBinomialHeap(heap, temp));}structNode*getMin(structNode*heap){if(!heap)returnNULL;structNode*min = heap;structNode*curr = heap->sibling;while(curr){if(curr->data < min->data) min = curr;
curr = curr->sibling;}return min;}structNode*extractMin(structNode*heap){if(!heap)returnNULL;structNode*min =getMin(heap);structNode*prev =NULL,*curr = heap;while(curr != min){
prev = curr;
curr = curr->sibling;}if(prev) prev->sibling = min->sibling;else heap = min->sibling;structNode*child = min->child;structNode*newHeap =NULL;while(child){structNode*next = child->sibling;
child->sibling = newHeap;
child->parent =NULL;
newHeap = child;
child = next;}
newHeap =adjustHeap(newHeap);return newHeap;}voiddeleteKey(structNode**heap,structNode*node){if(!*heap ||!node)return;
node->data = INT_MIN;structNode*parent = node->parent;while(parent && node->data < parent->data){int temp = node->data;
node->data = parent->data;
parent->data = temp;
node = parent;
parent = node->parent;}*heap =extractMin(*heap);}voidprintTree(structNode*h){while(h){printf("%d ", h->data);printTree(h->child);
h = h->sibling;}}voidprintHeap(structNode*h){printf("Binomial Heap: \n");while(h){printf("B%d: ", h->degree);printTree(h);printf("\n");
h = h->sibling;}}intmain(){structNode*hp =NULL;
hp =insert(hp,10);
hp =insert(hp,20);
hp =insert(hp,30);
hp =insert(hp,40);printHeap(hp);structNode*min =getMin(hp);printf("Min: %d\n", min->data);deleteKey(&hp, hp->sibling);printf("Binomial Heap after Delete operation\n");printHeap(hp);return0;}
Output
Following is the output of the above C code
Binomial Heap: B0: 10 B1: 20 B2: 30 B3: 40 Min: 10 Binomial Heap after Delete operation B0: 10 B1: 30 B2: 40
Time Complexity of Binomial Heap
Following are the time complexities of the Binomial Heap
- Insertion: O(log n)
- Deletion: O(log n)
- Decrease-Key: O(log n)
- Extract-Min: O(log n)
- Get-Min: O(1)
Applications of Binomial Heap
Binomial heaps are used in plenty of applications. Some of them are listed below
- Used in implementing priority queues.
- Dijkstra’s shortest path algorithm.
- Prim’s minimum spanning tree algorithm.
- Used in garbage collection.
Conclusion
In this tutorial, we have learned about Binomial Heap, its operations, and its implementation in C, C++, Java, and Python. We also discussed the time complexity of the Binomial Heap and its applications.
Leave a Reply