C++ Program to Implement Binomial Heap

«
»
This C++ Program demonstrates the implementation of Binomial Heap.

Here is source code of the C++ Program to demonstrate Binomial Heap. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. /*
  2.  * C++ Program to Implement Binomial Heap
  3.  */
  4. #include <iostream>
  5. #include <cstdlib>
  6. using namespace std;
  7. /*
  8.  * Node Declaration
  9.  */
  10. struct node
  11. {
  12.     int n;
  13.     int degree;
  14.     node* parent;
  15.     node* child;
  16.     node* sibling;
  17. };
  18. /*
  19.  * Class Declaration
  20.  */
  21. class BinomialHeap
  22. {
  23.     private:
  24.         node *H;
  25.         node *Hr;
  26.         int count;
  27.     public:
  28.         node* Initializeheap();
  29.         int Binomial_link(node*, node*);
  30.         node* Create_node(int);
  31.         node* Union(node*, node*);
  32.         node* Insert(node*, node*);
  33.         node* Merge(node*, node*);
  34.         node* Extract_Min(node*);
  35.         int Revert_list(node*);
  36.         int Display(node*);
  37.         node* Search(node*, int);
  38.         int Decrease_key(node*, int, int);
  39.         int Delete(node*, int);
  40.         BinomialHeap()
  41.         {
  42.             H = Initializeheap();
  43.             Hr = Initializeheap();
  44.             int count = 1;
  45.         }
  46. };
  47.  
  48. /*
  49.  * Initialize Heap
  50.  */
  51. node* BinomialHeap::Initializeheap()
  52. {
  53.     node* np;
  54.     np = NULL;
  55.     return np;
  56. }
  57. /*
  58.  * Linking nodes in Binomial Heap
  59.  */
  60. int BinomialHeap::Binomial_link(node* y, node* z)
  61. {
  62.     y->parent = z;
  63.     y->sibling = z->child;
  64.     z->child = y;
  65.     z->degree = z->degree + 1;
  66. }
  67. /*
  68.  * Create Nodes in Binomial Heap
  69.  */
  70. node* BinomialHeap::Create_node(int k)
  71. {
  72.     node* p = new node;
  73.     p->n = k;
  74.     return p;
  75. }
  76. /*
  77.  * Insert Nodes in Binomial Heap
  78.  */
  79. node* BinomialHeap::Insert(node* H, node* x)
  80. {
  81.     node* H1 = Initializeheap();
  82.     x->parent = NULL;
  83.     x->child = NULL;
  84.     x->sibling = NULL;
  85.     x->degree = 0;
  86.     H1 = x;
  87.     H = Union(H, H1);
  88.     return H;
  89. }
  90.  
  91. /*
  92.  * Union Nodes in Binomial Heap
  93.  */
  94. node* BinomialHeap::Union(node* H1, node* H2)
  95. {
  96.     node *H = Initializeheap();
  97.     H = Merge(H1, H2);
  98.     if (H == NULL)
  99.         return H;
  100.     node* prev_x;
  101.     node* next_x;
  102.     node* x;
  103.     prev_x = NULL;
  104.     x = H;
  105.     next_x = x->sibling;
  106.     while (next_x != NULL)
  107.     {
  108.         if ((x->degree != next_x->degree) || ((next_x->sibling != NULL)
  109.             && (next_x->sibling)->degree == x->degree))
  110.         {
  111.             prev_x = x;
  112.             x = next_x;
  113.         }
  114.         else
  115. 	    {
  116.             if (x->n <= next_x->n)
  117.             {
  118.                 x->sibling = next_x->sibling;
  119.                 Binomial_link(next_x, x);
  120.             }
  121.             else
  122.             {
  123.                 if (prev_x == NULL)
  124.                     H = next_x;
  125.                 else
  126.                     prev_x->sibling = next_x;
  127.                 Binomial_link(x, next_x);
  128.                 x = next_x;
  129.             }
  130. 	    }
  131.         next_x = x->sibling;
  132.     }
  133.     return H;
  134. }
  135. /*
  136.  * Merge Nodes in Binomial Heap
  137.  */
  138. node* BinomialHeap::Merge(node* H1, node* H2)
  139. {
  140.     node* H = Initializeheap();
  141.     node* y;
  142.     node* z;
  143.     node* a;
  144.     node* b;
  145.     y = H1;
  146.     z = H2;
  147.     if (y != NULL)
  148.     {
  149.         if (z != NULL)
  150.         {
  151.             if (y->degree <= z->degree)
  152.                 H = y;
  153.             else if (y->degree > z->degree)
  154.                 H = z;
  155.         }
  156.         else
  157.             H = y;
  158.     }
  159.     else
  160.         H = z;
  161.     while (y != NULL && z != NULL)
  162.     {
  163.         if (y->degree < z->degree)
  164.         {
  165.             y = y->sibling;
  166.         }
  167.         else if (y->degree == z->degree)
  168.         {
  169.             a = y->sibling;
  170.             y->sibling = z;
  171.             y = a;
  172.         }
  173.         else
  174.         {
  175.             b = z->sibling;
  176.             z->sibling = y;
  177.             z = b;
  178.         }
  179.     }
  180.     return H;
  181. }
  182. /*
  183.  * Display Binomial Heap
  184.  */
  185. int BinomialHeap::Display(node* H)
  186. {
  187.     if (H == NULL)
  188.     {
  189.         cout<<"The Heap is empty"<<endl;
  190.         return 0;
  191.     }
  192.     cout<<"The root nodes are: "<<endl;
  193.     node* p;
  194.     p = H;
  195.     while (p != NULL)
  196.     {
  197.         cout<<p->n;
  198.         if (p->sibling != NULL)
  199.             cout<<"-->";
  200.         p = p->sibling;
  201.     }
  202.     cout<<endl;
  203. }
  204. /*
  205.  * Extract Minimum
  206.  */
  207. node* BinomialHeap::Extract_Min(node* H1)
  208. {
  209.     Hr = NULL;
  210.     node* t = NULL;
  211.     node* x = H1;
  212.     if (x == NULL)
  213.     {
  214.         cout<<"Nothing to Extract"<<endl;
  215.         return x;
  216.     }
  217.     int min = x->n;
  218.     node* p = x;
  219.     while (p->sibling != NULL)
  220.     {
  221.         if ((p->sibling)->n < min)
  222.         {
  223.             min = (p->sibling)->n;
  224.             t = p;
  225.             x = p->sibling;
  226.         }
  227.         p = p->sibling;
  228.     }
  229.     if (t == NULL && x->sibling == NULL)
  230.         H1 = NULL;
  231.     else if (t == NULL)
  232.         H1 = x->sibling;
  233.     else if (t->sibling == NULL)
  234.         t = NULL;
  235.     else
  236.         t->sibling = x->sibling;
  237.     if (x->child != NULL)
  238.     {
  239.         Revert_list(x->child);
  240.         (x->child)->sibling = NULL;
  241.     }
  242.     H = Union(H1, Hr);
  243.     return x;
  244. }
  245. /*
  246.  * Reverse List
  247.  */
  248. int BinomialHeap::Revert_list(node* y)
  249. {
  250.     if (y->sibling != NULL)
  251.     {
  252.         Revert_list(y->sibling);
  253.         (y->sibling)->sibling = y;
  254.     }
  255.     else
  256.     {
  257.         Hr = y;
  258.     }
  259. }
  260.  
  261. /*
  262.  * Search Nodes in Binomial Heap
  263.  */
  264. node* BinomialHeap::Search(node* H, int k)
  265. {
  266.     node* x = H;
  267.     node* p = NULL;
  268.     if (x->n == k)
  269.     {
  270.         p = x;
  271.         return p;
  272.     }
  273.     if (x->child != NULL && p == NULL)
  274.         p = Search(x->child, k);
  275.     if (x->sibling != NULL && p == NULL)
  276.         p = Search(x->sibling, k);
  277.     return p;
  278. }
  279. /*
  280.  * Decrease key of a node
  281.  */
  282. int BinomialHeap::Decrease_key(node* H, int i, int k)
  283. {
  284.     int temp;
  285.     node* p;
  286.     node* y;
  287.     node* z;
  288.     p = Search(H, i);
  289.     if (p == NULL)
  290.     {
  291.         cout<<"Invalid choice of key"<<endl;
  292.         return 0;
  293.     }
  294.     if (k > p->n)
  295.     {
  296.         cout<<"Error!! New key is greater than current key"<<endl;
  297.         return 0;
  298.     }
  299.     p->n = k;
  300.     y = p;
  301.     z = p->parent;
  302.     while (z != NULL && y->n < z->n)
  303.     {
  304.         temp = y->n;
  305.         y->n = z->n;
  306.         z->n = temp;
  307.         y = z;
  308.         z = z->parent;
  309.     }
  310.     cout<<"Key reduced successfully"<<endl;
  311. }
  312. /*
  313.  * Delete Nodes in Binomial Heap
  314.  */
  315. int BinomialHeap::Delete(node* H, int k)
  316. {
  317.     node* np;
  318.     if (H == NULL)
  319.     {
  320.         cout<<"\nHEAP EMPTY!!!!!";
  321.         return 0;
  322.     }
  323.     Decrease_key(H, k, -1000);
  324.     np = Extract_Min(H);
  325.     if (np != NULL)
  326.         cout<<"Node Deleted Successfully"<<endl;
  327. }
  328. /*
  329.  * Main Contains Menu
  330.  */
  331. int main()
  332. {
  333.     int n, m, l, i;
  334.     BinomialHeap bh;
  335.     node* p;
  336.     node *H;
  337.     H = bh.Initializeheap();
  338.     char ch;
  339.     while (1)
  340.     {
  341.         cout<<"----------------------------"<<endl;
  342.         cout<<"Operations on Binomial heap"<<endl;
  343.         cout<<"----------------------------"<<endl;
  344.         cout<<"1)Insert Element in the heap"<<endl;
  345.         cout<<"2)Extract Minimum key node"<<endl;
  346.         cout<<"3)Decrease key of a node"<<endl;
  347.         cout<<"4)Delete a node"<<endl;
  348.         cout<<"5)Display Heap"<<endl;
  349.         cout<<"6)Exit"<<endl;
  350.         cout<<"Enter Your Choice: ";
  351.         cin>>l;
  352.         switch(l)
  353.         {
  354.         case 1:
  355.             cout<<"Enter the element to be inserted: ";
  356.             cin>>m;
  357.             p = bh.Create_node(m);
  358.             H = bh.Insert(H, p);
  359.             break;
  360.         case 2:
  361.             p = bh.Extract_Min(H);
  362.             if (p != NULL)
  363.                 cout<<"The node with minimum key: "<<p->n<<endl;
  364.             else
  365.                 cout<<"Heap is empty"<<endl;
  366.             break;
  367.         case 3:
  368.             cout<<"Enter the key to be decreased: ";
  369.             cin>>m;
  370.             cout<<"Enter new key value: ";
  371.             cin>>l;
  372.             bh.Decrease_key(H, m, l);
  373.             break;
  374.         case 4:
  375.             cout<<"Enter the key to be deleted: ";
  376.             cin>>m;
  377.             bh.Delete(H, m);
  378.             break;
  379.         case 5:
  380.             cout<<"The Heap is: "<<endl;
  381.             bh.Display(H);
  382.             break;
  383.         case 6:
  384.             exit(1);
  385.         default:
  386.             cout<<"Wrong Choice";
  387. 	  }
  388.     }
  389.     return 0;
  390. }

advertisement
$ g++ binomialheap.cpp
$ a.out
----------------------------
Operations on Binomial heap
----------------------------
1)Insert Element in the heap
2)Extract Minimum key node
3)Decrease key of a node
4)Delete a node
5)Display Heap
6)Exit
Enter Your Choice: 1
Enter the element to be inserted: 9
----------------------------
Operations on Binomial heap
----------------------------
1)Insert Element in the heap
2)Extract Minimum key node
3)Decrease key of a node
4)Delete a node
5)Display Heap
6)Exit
Enter Your Choice: 1
Enter the element to be inserted: 8
----------------------------
Operations on Binomial heap
----------------------------
1)Insert Element in the heap
2)Extract Minimum key node
3)Decrease key of a node
4)Delete a node
5)Display Heap
6)Exit
Enter Your Choice: 1
Enter the element to be inserted: 7
----------------------------
Operations on Binomial heap
----------------------------
1)Insert Element in the heap
2)Extract Minimum key node
3)Decrease key of a node
4)Delete a node
5)Display Heap
6)Exit
Enter Your Choice: 1
Enter the element to be inserted: 6
----------------------------
Operations on Binomial heap
----------------------------
1)Insert Element in the heap
2)Extract Minimum key node
3)Decrease key of a node
4)Delete a node
5)Display Heap
6)Exit
Enter Your Choice: 1
Enter the element to be inserted: 5
----------------------------
Operations on Binomial heap
----------------------------
1)Insert Element in the heap
2)Extract Minimum key node
3)Decrease key of a node
4)Delete a node
5)Display Heap
6)Exit
Enter Your Choice: 2
The node with minimum key: 5
----------------------------
Operations on Binomial heap
----------------------------
1)Insert Element in the heap
2)Extract Minimum key node
3)Decrease key of a node
4)Delete a node
5)Display Heap
6)Exit
Enter Your Choice: 4
Enter the key to be deleted: 6
Key reduced successfully
Node Deleted Successfully
----------------------------
Operations on Binomial heap
----------------------------
1)Insert Element in the heap
2)Extract Minimum key node
3)Decrease key of a node
4)Delete a node
5)Display Heap
6)Exit
Enter Your Choice: 2
The node with minimum key: 5
----------------------------
Operations on Binomial heap
----------------------------
1)Insert Element in the heap
2)Extract Minimum key node
3)Decrease key of a node
4)Delete a node
5)Display Heap
6)Exit
Enter Your Choice: 5
The root nodes are: 
5
----------------------------
Operations on Binomial heap
----------------------------
1)Insert Element in the heap
2)Extract Minimum key node
3)Decrease key of a node
4)Delete a node
5)Display Heap
6)Exit
Enter Your Choice: 6
 
 
------------------
(program exited with code: 1)
Press return to continue

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
advertisement
advertisement
If you wish to look at all C++ Programming examples, go to C++ Programs.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.