Category: Heap

Like Binomial heaps, Fibonacci heaps are collection of trees. They are loosely based on binomial heaps. Unlike trees within binomial heaps, trees within Fibonacci heaps are rooted but unordered.

Each node x in Fibonacci heaps contains a pointer p[x] to its parent, and a pointer child[x] to any one of its children. The children of x are linked together in a circular doubly linked list known as the child list of x.

Each child y in a child list has pointers left[y] and right[y] to point to the left and right siblings of y respectively. If node y is the only child, then left[y] = right[y] = y. The order in which siblings appear in a child list is arbitrary.

Structure of Fibonacci Heap

Each node x in Fibonacci heap contains the following fields:

• key[x]: key of node x
• degree[x]: number of children of x
• p[x]: parent of x
• child[x]: any one of the children of x
• left[x]: left sibling of x in the child list of x
• right[x]: right sibling of x in the child list of x
• mark[x]: boolean value to indicate whether x has lost a child since the last time x was made the child of another node

Each Fibonacci heap H is a set of rooted trees that are min-heap ordered. That is, each tree obeys the min-heap property: the key of a node is greater than or equal to the key of its parent.

The root list of H is a circular doubly linked list of elements of H containing exactly one root from each tree in the root list. The min pointer in H points to the root of the tree containing the minimum key.

This Fibonacci Heap H consists of five Fibonacci Heaps and 16 nodes. The line with arrow head indicates the root list. Minimum node in the list is denoted by min[H] which is holding 4.

The asymptotically fast algorithms for problems such as computing minimum spanning trees, finding single source of shortest paths etc. make essential use of Fibonacci heaps.

Operations on Fibonacci Heap

Following are the operations that can be performed on Fibonacci heap:

• Make-Fib-Heap().
• Fib-Heap-Insert(H, x).
• Fib-Heap-Extract-Min(H).
• Fib-Heap-Decrease-Key(H, x, k).
• Fib-Heap-Delete(H, x).

Insert Operation on Fibonacci Heap

Adds a new node x to the heap H. Its super fast, just inserts without much rearranging.

Algorithm for Insert Operation

Let’s assume that we have a Fibonacci heap H and a node x. The algorithm to insert node x into Fibonacci heap H is as follows:

1: Create a new Fibonacci Heap H' containing only x.
2: Set x.left = x and x.right = x (circular doubly linked list).
3: If H is empty, set H.min = x.
4: Otherwise, Insert x into the root list of H and update H.min if x.key < H.min.key.
5: Increase the total node count of H.

Code for Insert Operation

Let’s write a simple code to insert a node into Fibonacci heap.

CC++JavaPython

#include <stdio.h>#include <stdlib.h>#include <math.h>structNode{int key, degree;structNode*parent,*child,*left,*right;int mark;};structFibonacciHeap{structNode* min;int nodeCount;};structNode*createNode(int key){structNode* newNode =(structNode*)malloc(sizeof(structNode));
   newNode->key = key;
   newNode->degree =0;
   newNode->parent = newNode->child =NULL;
   newNode->mark =0;
   newNode->left = newNode->right = newNode;return newNode;}structFibonacciHeap*createHeap(){structFibonacciHeap* heap =(structFibonacciHeap*)malloc(sizeof(structFibonacciHeap));
   heap->min =NULL;
   heap->nodeCount =0;return heap;}voidinsert(structFibonacciHeap* H,int key){structNode* x =createNode(key);if(!H->min){
      H->min = x;}else{
      x->right = H->min->right;
      x->left = H->min;
      H->min->right->left = x;
      H->min->right = x;if(x->key < H->min->key){
         H->min = x;}}
   H->nodeCount++;}voidprintHeap(structFibonacciHeap* H){if(!H->min){printf("Heap is empty!\n");return;}structNode* temp = H->min;printf("Fibonacci Heap Root List: ");do{printf("%d ", temp->key);
      temp = temp->right;}while(temp != H->min);printf("\n");}intmain(){structFibonacciHeap* fibHeap =createHeap();insert(fibHeap,10);insert(fibHeap,3);insert(fibHeap,15);insert(fibHeap,7);printHeap(fibHeap);printf("Minimum value in heap: %d\n", fibHeap->min->key);return0;}

Output

Following is the output of the above code:

Fibonacci Heap Root List: 3 7 10 15
Minimum value in heap: 3

Extract Minimum Operation on Fibonacci Heap

Removes the node containing the minimum key from the heap H. Its a bit complex operation as it involves rearranging the tree structure.

Algorithm

Let’s assume that we have a Fibonacci heap H. The algorithm to extract minimum node from Fibonacci heap H is as follows:

1: z = H.min
2: If z != NULL
   1 - For each child x of z, add x to the root list of H.
   2 - Remove z from the root list of H.
   3 - If z = z.right, then H.min = NULL.
   4 - Else, H.min = z.right and Consolidate(H).
   5 - Decrease the total node count of H.
3: Return z.

Code for Extract Minimum Operation

Let’s write a simple code to extract minimum node from Fibonacci heap.

CC++JavaPython

#include <stdio.h>#include <stdlib.h>structNode{int key, degree;structNode*parent,*child,*left,*right;int mark;};structFibonacciHeap{structNode* min;int nodeCount;};structNode*createNode(int key){structNode* newNode =(structNode*)malloc(sizeof(structNode));
   newNode->key = key;
   newNode->degree =0;
   newNode->parent = newNode->child =NULL;
   newNode->mark =0;
   newNode->left = newNode->right = newNode;return newNode;}structFibonacciHeap*createHeap(){structFibonacciHeap* heap =(structFibonacciHeap*)malloc(sizeof(structFibonacciHeap));
   heap->min =NULL;
   heap->nodeCount =0;return heap;}voidinsert(structFibonacciHeap* H,int key){structNode* x =createNode(key);if(!H->min){
      H->min = x;}else{
      x->right = H->min->right;
      x->left = H->min;
      H->min->right->left = x;
      H->min->right = x;if(x->key < H->min->key){
         H->min = x;}}
   H->nodeCount++;}voidprintHeap(structFibonacciHeap* H){if(!H->min){printf("Heap is empty!\n");return;}structNode* temp = H->min;printf("Fibonacci Heap Root List: ");do{printf("%d ", temp->key);
      temp = temp->right;}while(temp != H->min);printf("\n");}structNode*extractMin(structFibonacciHeap* H){structNode* z = H->min;if(z){structNode* x = z->child;if(x){structNode* temp = x;do{structNode* next = temp->right;
            temp->left->right = temp->right;
            temp->right->left = temp->left;
            temp->left = H->min;
            temp->right = H->min->right;
            H->min->right->left = temp;
            H->min->right = temp;
            temp->parent =NULL;
            temp = next;}while(temp != x);}
      z->left->right = z->right;
      z->right->left = z->left;if(z == z->right){
         H->min =NULL;}else{
         H->min = z->right;// consolidate(H); }
      H->nodeCount--;}return z;}intmain(){structFibonacciHeap* fibHeap =createHeap();insert(fibHeap,10);insert(fibHeap,3);insert(fibHeap,15);insert(fibHeap,7);printHeap(fibHeap);structNode* minNode =extractMin(fibHeap);if(minNode){printf("Minimum value extracted: %d\n", minNode->key);free(minNode);}else{printf("Heap is empty!\n");}printHeap(fibHeap);return0;}

Output

Following is the output of the above code:

Fibonacci Heap Root List: 3 7 10 15
Minimum value extracted: 3
Fibonacci Heap Root List: 7 10 15

Decrease Key Operation on Fibonacci Heap

Decreases the key of node x to the new key k. Its a bit complex operation as it involves rearranging the tree structure.

Algorithm for Decrease Key Operation

Let’s assume that we have a Fibonacci heap H, a node x and a new key k. The algorithm to decrease key of node x to k in Fibonacci heap H is as follows:

1: x.key = k
2: y = x.parent
3: If y != NULL and x.key < y.key
   1 - Cut x from its parent y.
   2 - Cascading-Cut(H, y).
4: If x.key < H.min.key, set H.min = x.

Code for Decrease Key Operation

Let’s write a simple code to decrease key of a node in Fibonacci heap.

CC++JavaPython

#include <stdio.h>#include <stdlib.h>#include <limits.h>structNode{int key, degree;structNode*parent,*child,*left,*right;int mark;};structFibonacciHeap{structNode* min;int nodeCount;};structNode*createNode(int key){structNode* newNode =(structNode*)malloc(sizeof(structNode));
   newNode->key = key;
   newNode->degree =0;
   newNode->parent = newNode->child =NULL;
   newNode->mark =0;
   newNode->left = newNode->right = newNode;return newNode;}structFibonacciHeap*createHeap(){structFibonacciHeap* heap =(structFibonacciHeap*)malloc(sizeof(structFibonacciHeap));
   heap->min =NULL;
   heap->nodeCount =0;return heap;}voidinsert(structFibonacciHeap* H,structNode* x){if(!H->min){
      H->min = x;}else{
      x->right = H->min->right;
      x->left = H->min;
      H->min->right->left = x;
      H->min->right = x;if(x->key < H->min->key){
         H->min = x;}}
   H->nodeCount++;}voidcut(structFibonacciHeap* H,structNode* x,structNode* y){if(x->right == x){
      y->child =NULL;}else{
      x->right->left = x->left;
      x->left->right = x->right;if(y->child == x){
         y->child = x->right;}}
   y->degree--;

   x->left = H->min;
   x->right = H->min->right;
   H->min->right->left = x;
   H->min->right = x;
   x->parent =NULL;
   x->mark =0;}voidcascadingCut(structFibonacciHeap* H,structNode* y){structNode* z = y->parent;if(z){if(!y->mark){
         y->mark =1;}else{cut(H, y, z);cascadingCut(H, z);}}}voiddecreaseKey(structFibonacciHeap* H,structNode* x,int newKey){if(newKey > x->key){printf("New key is greater than current key!\n");return;}
   x->key = newKey;structNode* y = x->parent;if(y && x->key < y->key){cut(H, x, y);cascadingCut(H, y);}if(x->key < H->min->key){
      H->min = x;}}voidprintHeap(structFibonacciHeap* H){if(!H->min){printf("Heap is empty!\n");return;}structNode* temp = H->min;printf("Fibonacci Heap Root List: ");do{printf("%d ", temp->key);
      temp = temp->right;}while(temp != H->min);printf("\n");}intmain(){structFibonacciHeap* fibHeap =createHeap();structNode* n1 =createNode(10);structNode* n2 =createNode(3);structNode* n3 =createNode(15);structNode* n4 =createNode(7);insert(fibHeap, n1);insert(fibHeap, n2);insert(fibHeap, n3);insert(fibHeap, n4);printHeap(fibHeap);decreaseKey(fibHeap, n3,1);printf("After Decrease-Key:\n");printHeap(fibHeap);return0;}

Output

Following is the output of the above code:

Fibonacci Heap Root List: 3 7 10 15
Fibonacci Heap Root List: 1 10 7 3

Delete Operation on Fibonacci Heap

Deletes the node x from the heap H. Its a bit complex operation as it involves rearranging the tree structure.

Algorithm for Delete Operation

Let’s assume that we have a Fibonacci heap H and a node x. The algorithm to delete node x from Fibonacci heap H is as follows:

1: Decrease key of node x to -.
2: Extract minimum node from heap H.

Code for Delete Operation

Let’s write a simple code to delete a node from Fibonacci heap.

CC++JavaPython

#include <stdio.h>#include <stdlib.h>#include <limits.h>typedefstructNode{int key, degree;structNode*parent,*child,*left,*right;int mark;} Node;typedefstructFibonacciHeap{
    Node *min;int nodeCount;} FibonacciHeap;

Node*createNode(int key){
    Node* node =(Node*)malloc(sizeof(Node));
    node->key = key;
    node->degree =0;
    node->parent = node->child =NULL;
    node->mark =0;
    node->left = node->right = node;return node;}

FibonacciHeap*createHeap(){
    FibonacciHeap* heap =(FibonacciHeap*)malloc(sizeof(FibonacciHeap));
    heap->min =NULL;
    heap->nodeCount =0;return heap;}voidinsert(FibonacciHeap* heap, Node* x){if(heap->min ==NULL){
        heap->min = x;}else{
        x->right = heap->min->right;
        x->left = heap->min;
        heap->min->right->left = x;
        heap->min->right = x;if(x->key < heap->min->key){
            heap->min = x;}}
    heap->nodeCount++;}voiddecreaseKey(FibonacciHeap* heap, Node* x,int newKey){if(newKey > x->key){printf("New key is greater than current key!\n");return;}
    x->key = newKey;
    Node* y = x->parent;if(y !=NULL&& x->key < y->key){// Implement cut and cascadingCut}if(x->key < heap->min->key){
        heap->min = x;}}

Node*extractMin(FibonacciHeap* heap){
    Node* z = heap->min;if(z !=NULL){if(z->child !=NULL){// Merge child nodes into root list}
        z->left->right = z->right;
        z->right->left = z->left;if(z == z->right){
            heap->min =NULL;}else{
            heap->min = z->right;// Implement consolidate function}
        heap->nodeCount--;}return z;}voiddeleteNode(FibonacciHeap* heap, Node* x){decreaseKey(heap, x, INT_MIN);extractMin(heap);}voidprintHeap(FibonacciHeap* heap){if(heap->min ==NULL){printf("Heap is empty!\n");return;}
    Node* temp = heap->min;printf("Fibonacci Heap Root List: ");do{printf("%d ", temp->key);
        temp = temp->right;}while(temp != heap->min);printf("\n");}intmain(){
    FibonacciHeap* fibHeap =createHeap();
    Node* n1 =createNode(10);
    Node* n2 =createNode(3);
    Node* n3 =createNode(15);
    Node* n4 =createNode(7);insert(fibHeap, n1);insert(fibHeap, n2);insert(fibHeap, n3);insert(fibHeap, n4);printHeap(fibHeap);deleteNode(fibHeap, n3);printf("After Delete:\n");printHeap(fibHeap);return0;}

Output

Following is the output of the above code:

Fibonacci Heap Root List: 3 7 10 15
Minimum value extracted: 3
Fibonacci Heap Root List: 7 10 15

Time Complexity of Fibonacci Heap

Let’s analyze the time complexity of various operations in Fibonacci heap:

• Insert Operation: O(1)
• Extract Minimum Operation: O(log n)
• Decrease Key Operation: O(1)
• Delete Operation: O(log n)

Thus, the Fibonacci heap is a data structure that supports insert, extract minimum, decrease key, and delete operations in amortized O(log n) time complexity.

Applications of Fibonacci Heap

Following are some of the applications of Fibonacci heap:

• It is used in Dijkstra’s algorithm to find the shortest path in a graph.
• Also, used in Prim’s algorithm to find the minimum spanning tree of a graph.
• Used in network routing algorithms.

Conclusion

In this tutorial, we learned about Fibonacci heap, its operations, and its time complexity. We also implemented the Fibonacci heap in C, C++, Java, and Python programming languages. We also discussed the applications of Fibonacci heap in various algorithms.

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 B_k is defined as follows

• B₀ is a single node.
• B_k is formed by linking two binomial trees B_k-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 B_k has 2_k 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 B_k 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.

CC++JavaPython

#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.

CC++JavaPython

#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.

CC++JavaPython

#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.

CC++JavaPython

#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.

What is Binary Heap?

Heap or Binary Heap is a special case of balanced binary tree data structure. It is a complete binary tree structure. Means, all levels of the tree are fully filled except possibly for the last level which has all keys as left as possible.

In this structure, the root node is compared to its children, meaning that the root node will be either the smallest or the largest element in the tree. The root node will be the topmost element of all the nodes in the tree.

• Max-Heap: key(a) key(b)
• Min-Heap: key(a) key(b)

Representation of Binary Heap

Binary heap is represented as an array. The root element will be at Arr[0]. For any given node at position i, the left child will be at position 2*i + 1 and the right child at position 2*i + 2.

Binary Min-Heap Representation

For a Min-Heap, the root element will be the minimum element in the tree. The left child will be greater than the parent and the right child will be greater than the parent. The representation of a Min-Heap is as follows:

Binary Max-Heap Representation

For a Max-Heap, the root element will be the maximum element in the tree. The left child will be less than the parent and the right child will be less than the parent. The representation of a Max-Heap is as follows:

Operations on Binary Heap

There are mainly three operations that can be performed on a binary heap:

• Insert: Inserting a new element in the heap.
• Delete: Deleting the root element of the heap.
• Peek: Getting the root element of the heap.

Heapify Operation

Heapify operations are used for maintaining the heap property of the binary heap. There are two types of heapify operations:

• Min-Heapify: It is also known as Bubble Down. It is used to maintain the Min-Heap property of the binary heap.
• Max-Heapify: It is also known as Bubble Up. It is used to maintain the Max-Heap property of the binary heap.

Insert Operation on Binary Heap

Inserting a new element in the heap is done by inserting the element at the end of the heap and then heapifying the heap.

The heapifying process is done by comparing the new element with its parent and swapping the elements if the new element is smaller than the parent. The process is repeated until the new element is greater than its parent.

Algorithm for Insert Operation

Following is the algorithm for Insert Operation on Binary Heap:

1.Insert the new element at the end of the heap.
2.Initialize i as the index of the new element.
3.WHILE i is not 0 AND heap[parent(i)] > heap[i]
4.SWAP heap[i] and heap[parent(i)]
5.Update i to parent(i)

Code for Insert Operation

Following is the code for Insert Operation on Binary Heap:

CC++JavaPython

//C Program to perform Insert Operation on Binary Heap#include <stdio.h>intinsert(int heap[],int n,int key){
   n = n +1;int i = n -1;
   heap[i]= key;while(i !=0&& heap[(i-1)/2]> heap[i]){int temp = heap[i];
      heap[i]= heap[(i-1)/2];
      heap[(i-1)/2]= temp;
      i =(i-1)/2;}return n;}intmain(){int heap[100]={10,20,15,40,50,100,25};int n =7;int key =12;
   n =insert(heap, n, key);printf("Heap after Insert Operation: ");for(int i =0; i < n; i++){printf("%d ", heap[i]);}return0;}

Output

Following is the output of the above C program:

Heap after Insert Operation: 10 12 15 20 50 100 25 40

Delete Operation on Binary Heap

Deleting the root element of the heap is done by replacing the root element with the last element of the heap and then heapifying the heap.

The heapifying process is done by comparing the root element with its children and swapping the elements if the root element is greater than its children. The process is repeated until the root element is less than its children.

Algorithm for Delete Operation

Following is the algorithm for Delete Operation on Binary Heap:

START
   Replace the root element with the last element of the heap.
   Initialize i as 0.
   WHILE 2*i + 1 < n
      Set left as 2*i + 1.
      Set right as 2*i + 2.
      Set min as left.
      IF right < n AND heap[right] < heap[left]
         Set min as right.
      IF heap[i] > heap[min]
         SWAP heap[i] and heap[min]
         Update i to min
      ELSE
         BREAK
END

Code for Delete Operation

Following is the code for Delete Operation on Binary Heap:

CC++JavaPython

//C Program to perform Delete Operation on Binary Heap#include <stdio.h>intinsert(int heap[],int n,int key){
   n = n +1;int i = n -1;
   heap[i]= key;while(i !=0&& heap[(i-1)/2]> heap[i]){int temp = heap[i];
      heap[i]= heap[(i-1)/2];
      heap[(i-1)/2]= temp;
      i =(i-1)/2;}return n;}intdelete(int heap[],int n){int root = heap[0];
   heap[0]= heap[n-1];
   n = n -1;int i =0;while(2*i +1< n){int left =2*i +1;int right =2*i +2;int min = left;if(right < n && heap[right]< heap[left]){
         min = right;}if(heap[i]> heap[min]){int temp = heap[i];
         heap[i]= heap[min];
         heap[min]= temp;
         i = min;}else{break;}}return n;}intmain(){int heap[100]={10,20,15,40,50,100,25};int n =7;printf("Heap before Delete Operation: ");for(int i =0; i < n; i++){printf("%d ", heap[i]);}printf("\n");
   n =delete(heap, n);printf("Heap after Delete Operation: ");for(int i =0; i < n; i++){printf("%d ", heap[i]);}return0;}

Output

Following is the output of the above C program:

Heap before Delete Operation: 10 20 15 40 50 100 25
Heap after Delete Operation: 15 20 25 40 50 100

Applications of Binary Heap

Binary Heap is used for many applications. Some of the common applications of Binary Heap are as follows:

• Heap Sort: Heap sort is used to sort an array. It is used in the heap data structure. Binary heap is used to implement heap sort.
• Priority Queue: Binary heap is used for implementing priority queues. It is used in Dijkstra’s algorithm, Prim’s algorithm, etc.
• Graph Algorithms: Binary Heap is used in graph algorithms like Kruskal’s algorithm, Prim’s algorithm, etc.

Conclusion

Binary heaps are useful data structures which can be used to manage the priority of the element. It is the backbone of many algorithms and data structures. It is used in many applications like heap sort, priority queues, graph algorithms, etc.

Heap is a special case of balanced binary tree data structure where the root-node key is compared with its children and arranged accordingly. If α has child node β then −

key(α) ≥ key(β)

As the value of parent is greater than that of child, this property generates Max Heap. Based on this criteria, a heap can be of two types −

For Input → 35 33 42 10 14 19 27 44 26 31

Min-Heap − Where the value of the root node is less than or equal to either of its children.

Max-Heap − Where the value of the root node is greater than or equal to either of its children.

Both trees are constructed using the same input and order of arrival.

Max Heap Construction Algorithm

We shall use the same example to demonstrate how a Max Heap is created. The procedure to create Min Heap is similar but we go for min values instead of max values.

We are going to derive an algorithm for max heap by inserting one element at a time. At any point of time, heap must maintain its property. While insertion, we also assume that we are inserting a node in an already heapified tree.

Step 1 − Create a new node at the end of heap.
Step 2 − Assign new value to the node.
Step 3 − Compare the value of this child node with its parent.
Step 4 − If value of parent is less than child, then swap them.
Step 5 − Repeat step 3 & 4 until Heap property holds.

Note − In Min Heap construction algorithm, we expect the value of the parent node to be less than that of the child node.

Let’s understand Max Heap construction by an animated illustration. We consider the same input sample that we used earlier.

Example

Following are the implementations of this operation in various programming languages −

CC++JavaPython

//C code for Max Heap construction  Algorithm#include <stdio.h>#include <stdlib.h>// Structure to represent a heaptypedefstruct{int* array;// Array to store heap elementsint capacity;// Maximum capacity of the heapint size;// Current size of the heap} Heap;// Function to create a new heap
Heap*createHeap(int capacity){
    Heap* heap =(Heap*)malloc(sizeof(Heap));
    heap->array =(int*)malloc(capacity *sizeof(int));
    heap->capacity = capacity;
    heap->size =0;return heap;}// Function to swap two elements in the heapvoidswap(int* a,int* b){int temp =*a;*a =*b;*b = temp;}// Function to heapify a subtree rooted at index ivoidheapify(Heap* heap,int i){int largest = i;int left =2* i +1;int right =2* i +2;// Check if the left child is larger than the rootif(left < heap->size && heap->array[left]> heap->array[largest])
        largest = left;// Check if the right child is larger than the largest so farif(right < heap->size && heap->array[right]> heap->array[largest])
        largest = right;// If the largest is not the root, swap the root with the largestif(largest != i){swap(&heap->array[i],&heap->array[largest]);heapify(heap, largest);}}// Function to insert a new element into the heapvoidinsert(Heap* heap,int value){if(heap->size == heap->capacity){printf("Heap is full. Cannot insert more elements.\n");return;}// Insert the new element at the endint i = heap->size++;
    heap->array[i]= value;// Fix the heap property if it is violatedwhile(i !=0&& heap->array[(i -1)/2]< heap->array[i]){swap(&heap->array[i],&heap->array[(i -1)/2]);
        i =(i -1)/2;}}// Function to extract the maximum element from the heapintextractMax(Heap* heap){if(heap->size ==0){printf("Heap is empty. Cannot extract maximum element.\n");return-1;}// Store the root elementint max = heap->array[0];// Replace the root with the last element
    heap->array[0]= heap->array[heap->size -1];
    heap->size--;// Heapify the rootheapify(heap,0);return max;}// Function to print the elements of the heapvoidprintHeap(Heap* heap){printf("Heap elements: ");for(int i =0; i < heap->size; i++){printf("%d ", heap->array[i]);}printf("\n");}// Example usage of the heapintmain(){
    Heap* heap =createHeap(10);insert(heap,35);insert(heap,33);insert(heap,42);insert(heap,10);insert(heap,14);insert(heap,19);insert(heap,27);insert(heap,44);insert(heap,26);insert(heap,31);printHeap(heap);int max =extractMax(heap);printf("Maximum element: %d\n", max);return0;}

Output

Heap elements: 44 42 35 33 31 19 27 10 26 14 
Maximum element: 44

Max Heap Deletion Algorithm

Let us derive an algorithm to delete from max heap. Deletion in Max (or Min) Heap always happens at the root to remove the Maximum (or minimum) value.

Step 1 − Remove root node.
Step 2 − Move the last element of last level to root.
Step 3 − Compare the value of this child node with its parent.
Step 4 − If value of parent is less than child, then swap them.
Step 5 − Repeat step 3 & 4 until Heap property holds.

Example

Following are the implementations of this operation in various programming languages −

CC++JavaPython

//C code for Max Heap Deletion Algorithm#include <stdio.h>#include <stdlib.h>// Structure to represent a heaptypedefstruct{int* array;// Array to store heap elementsint capacity;// Maximum capacity of the heapint size;// Current size of the heap} Heap;// create a new heap
Heap*createHeap(int capacity){
    Heap* heap =(Heap*)malloc(sizeof(Heap));
    heap->array =(int*)malloc(capacity *sizeof(int));
    heap->capacity = capacity;
    heap->size =0;return heap;}// swap two elements in the heapvoidswap(int* a,int* b){int temp =*a;*a =*b;*b = temp;}// Heapify a subtree rooted at index ivoidheapify(Heap* heap,int i){int largest = i;int left =2* i +1;int right =2* i +2;// Check if the left child is larger than the rootif(left < heap->size && heap->array[left]> heap->array[largest])
        largest = left;// Check if the right child is larger than the largest so farif(right < heap->size && heap->array[right]> heap->array[largest])
        largest = right;// If the largest is not the root, swap the root with the largestif(largest != i){swap(&heap->array[i],&heap->array[largest]);heapify(heap, largest);}}// Function to insert a new element into the heapvoidinsert(Heap* heap,int value){if(heap->size == heap->capacity){printf("Heap is full. Cannot insert more elements.\n");return;}// Insert the new element at the endint i = heap->size++;
    heap->array[i]= value;// Fix the heap property if it is violatedwhile(i !=0&& heap->array[(i -1)/2]< heap->array[i]){swap(&heap->array[i],&heap->array[(i -1)/2]);
        i =(i -1)/2;}}// delete the maximum element from the heapintdeleteMax(Heap* heap){if(heap->size ==0){printf("Heap is empty. Cannot extract maximum element.\n");return-1;}// Store the root elementint max = heap->array[0];// Replace the root with the last element
    heap->array[0]= heap->array[heap->size -1];
    heap->size--;// Heapify the rootheapify(heap,0);return max;}// print the elements of the heapvoidprintHeap(Heap* heap){for(int i =0; i < heap->size; i++){printf("%d ", heap->array[i]);}printf("\n");}// Deallocate memory occupied by the heapvoiddestroyHeap(Heap* heap){free(heap->array);free(heap);}// Example usage of the heapintmain(){
    Heap* heap =createHeap(10);insert(heap,35);insert(heap,33);insert(heap,42);insert(heap,10);insert(heap,14);insert(heap,19);insert(heap,27);insert(heap,44);insert(heap,26);insert(heap,31);printf("Heap elements before deletion: ");printHeap(heap);// Deleting the maximum element in the heapint max =deleteMax(heap);printf("Maximum element: %d\n", max);printf("Heap elements after deletion: ");printHeap(heap);destroyHeap(heap);return0;}

Output

Heap elements before deletion: 44 42 35 33 31 19 27 10 26 14 
Maximum element: 44
Heap elements after deletion: 42 33 35 26 31 19 27 10 14