C++ Program to Implement Fibonacci Heap

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

Here is source code of the C++ Program to demonstrate Fibonacci 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 Fibonacci Heap
  3.  */
  4. #include <iostream>
  5. #include <cmath>
  6. #include <cstdlib>
  7. using namespace std;
  8. /*
  9.  * Node Declaration
  10.  */
  11. struct node
  12. {
  13.     int n;
  14.     int degree;
  15.     node* parent;
  16.     node* child;
  17.     node* left;
  18.     node* right;
  19.     char mark;
  20.     char C;
  21. };
  22. /*
  23.  * Class Declaration
  24.  */
  25. class FibonacciHeap
  26. {
  27.     private:
  28.         int nH;
  29.         node *H;
  30.     public:
  31.         node* InitializeHeap();
  32.         int Fibonnaci_link(node*, node*, node*);
  33.         node *Create_node(int);
  34.         node *Insert(node *, node *);
  35.         node *Union(node *, node *);
  36.         node *Extract_Min(node *);
  37.         int Consolidate(node *);
  38.         int Display(node *);
  39.         node *Find(node *, int);
  40.         int Decrease_key(node *, int, int);
  41.         int Delete_key(node *,int);
  42.         int Cut(node *, node *, node *);
  43.         int Cascase_cut(node *, node *);
  44.         FibonacciHeap()
  45.         {
  46.             H = InitializeHeap();
  47.         }
  48. };
  49. /*
  50.  * Initialize Heap
  51.  */
  52. node* FibonacciHeap::InitializeHeap()
  53. {
  54.     node* np;
  55.     np = NULL;
  56.     return np;
  57. }
  58. /*
  59.  * Create Node
  60.  */
  61. node* FibonacciHeap::Create_node(int value)
  62. {
  63.     node* x = new node;
  64.     x->n = value;
  65.     return x;
  66. }
  67. /*
  68.  * Insert Node
  69.  */
  70. node* FibonacciHeap::Insert(node* H, node* x)
  71. {
  72.     x->degree = 0;
  73.     x->parent = NULL;
  74.     x->child = NULL;
  75.     x->left = x;
  76.     x->right = x;
  77.     x->mark = 'F';
  78.     x->C = 'N';
  79.     if (H != NULL)
  80.     {
  81.         (H->left)->right = x;
  82.         x->right = H;
  83.         x->left = H->left;
  84.         H->left = x;
  85.         if (x->n < H->n)
  86.             H = x;
  87.     }
  88.     else
  89.     {
  90.         H = x;
  91.     }
  92.     nH = nH + 1;
  93.     return H;
  94. }
  95. /*
  96.  * Link Nodes in Fibonnaci Heap
  97.  */
  98. int FibonacciHeap::Fibonnaci_link(node* H1, node* y, node* z)
  99. {
  100.     (y->left)->right = y->right;
  101.     (y->right)->left = y->left;
  102.     if (z->right == z)
  103.         H1 = z;
  104.     y->left = y;
  105.     y->right = y;
  106.     y->parent = z;
  107.     if (z->child == NULL)
  108.         z->child = y;
  109.     y->right = z->child;
  110.     y->left = (z->child)->left;
  111.     ((z->child)->left)->right = y;
  112.     (z->child)->left = y;
  113.     if (y->n < (z->child)->n)
  114.         z->child = y;
  115.     z->degree++;
  116. }
  117. /*
  118.  * Union Nodes in Fibonnaci Heap
  119.  */
  120. node* FibonacciHeap::Union(node* H1, node* H2)
  121. {
  122.     node* np;
  123.     node* H = InitializeHeap();
  124.     H = H1;
  125.     (H->left)->right = H2;
  126.     (H2->left)->right = H;
  127.     np = H->left;
  128.     H->left = H2->left;
  129.     H2->left = np;
  130.     return H;
  131. }
  132. /*
  133.  * Display Fibonnaci Heap
  134.  */
  135. int FibonacciHeap::Display(node* H)
  136. {
  137.     node* p = H;
  138.     if (p == NULL)
  139.     {
  140.         cout<<"The Heap is Empty"<<endl;
  141.         return 0;
  142.     }
  143.     cout<<"The root nodes of Heap are: "<<endl;
  144.     do
  145.     {
  146.         cout<<p->n;
  147.         p = p->right;
  148.         if (p != H)
  149.         {
  150.             cout<<"-->";
  151.         }
  152.     }
  153.     while (p != H && p->right != NULL);
  154.     cout<<endl;
  155. }
  156. /*
  157.  * Extract Min Node in Fibonnaci Heap
  158.  */
  159. node* FibonacciHeap::Extract_Min(node* H1)
  160. {
  161.     node* p;
  162.     node* ptr;
  163.     node* z = H1;
  164.     p = z;
  165.     ptr = z;
  166.     if (z == NULL)
  167.         return z;
  168.     node* x;
  169.     node* np;
  170.     x = NULL;
  171.     if (z->child != NULL)
  172.         x = z->child;
  173.     if (x != NULL)
  174.     {
  175.         ptr = x;
  176.         do
  177.         {
  178.             np = x->right;
  179.             (H1->left)->right = x;
  180.             x->right = H1;
  181.             x->left = H1->left;
  182.             H1->left = x;
  183.             if (x->n < H1->n)
  184.                 H1 = x;
  185.             x->parent = NULL;
  186.             x = np;
  187.         }
  188.         while (np != ptr);
  189.     }
  190.     (z->left)->right = z->right;
  191.     (z->right)->left = z->left;
  192.     H1 = z->right;
  193.     if (z == z->right && z->child == NULL)
  194.         H = NULL;
  195.     else
  196.     {
  197.         H1 = z->right;
  198.         Consolidate(H1);
  199.     }
  200.     nH = nH - 1;
  201.     return p;
  202. }
  203. /*
  204.  * Consolidate Node in Fibonnaci Heap
  205.  */
  206. int FibonacciHeap::Consolidate(node* H1)
  207. {
  208.     int d, i;
  209.     float f = (log(nH)) / (log(2));
  210.     int D = f;
  211.     node* A[D];
  212.     for (i = 0; i <= D; i++)
  213.         A[i] = NULL;
  214.     node* x = H1;
  215.     node* y;
  216.     node* np;
  217.     node* pt = x;
  218.     do
  219.     {
  220.         pt = pt->right;
  221.         d = x->degree;
  222.         while (A[d] != NULL)
  223.         {
  224.             y = A[d];
  225.             if (x->n > y->n)
  226.             {
  227.                 np = x;
  228.                 x = y;
  229.                 y = np;
  230.             }
  231.             if (y == H1)
  232.                 H1 = x;
  233.             Fibonnaci_link(H1, y, x);
  234.             if (x->right == x)
  235.                 H1 = x;
  236.                 A[d] = NULL;
  237.             d = d + 1;
  238.         }
  239.         A[d] = x;
  240.         x = x->right;
  241.     }
  242.     while (x != H1);
  243.     H = NULL;
  244.     for (int j = 0; j <= D; j++)
  245.     {
  246.         if (A[j] != NULL)
  247.         {
  248.             A[j]->left = A[j];
  249.             A[j]->right =A[j];
  250.             if (H != NULL)
  251.             {
  252.                 (H->left)->right = A[j];
  253.                 A[j]->right = H;
  254.                 A[j]->left = H->left;
  255.                 H->left = A[j];
  256.                 if (A[j]->n < H->n)
  257.                 H = A[j];
  258.             }
  259.             else
  260.             {
  261.                 H = A[j];
  262.             }
  263.             if(H == NULL)
  264.                 H = A[j];
  265.             else if (A[j]->n < H->n)
  266.                 H = A[j];
  267.         }
  268.     }
  269. }
  270.  
  271. /*
  272.  * Decrease key of Nodes in Fibonnaci Heap
  273.  */
  274. int FibonacciHeap::Decrease_key(node*H1, int x, int k)
  275. {
  276.     node* y;
  277.     if (H1 == NULL)
  278.     {
  279.         cout<<"The Heap is Empty"<<endl;
  280.         return 0;
  281.     }
  282.     node* ptr = Find(H1, x);
  283.     if (ptr == NULL)
  284.     {
  285.         cout<<"Node not found in the Heap"<<endl;
  286.         return 1;
  287.     }
  288.     if (ptr->n < k)
  289.     {
  290.         cout<<"Entered key greater than current key"<<endl;
  291.         return 0;
  292.     }
  293.     ptr->n = k;
  294.     y = ptr->parent;
  295.     if (y != NULL && ptr->n < y->n)
  296.     {
  297.         Cut(H1, ptr, y);
  298.         Cascase_cut(H1, y);
  299.     }
  300.     if (ptr->n < H->n)
  301.         H = ptr;
  302.     return 0;
  303. }
  304. /*
  305.  * Cut Nodes in Fibonnaci Heap
  306.  */
  307. int FibonacciHeap::Cut(node* H1, node* x, node* y)
  308. {
  309.     if (x == x->right)
  310.         y->child = NULL;
  311.     (x->left)->right = x->right;
  312.     (x->right)->left = x->left;
  313.     if (x == y->child)
  314.         y->child = x->right;
  315.     y->degree = y->degree - 1;
  316.     x->right = x;
  317.     x->left = x;
  318.     (H1->left)->right = x;
  319.     x->right = H1;
  320.     x->left = H1->left;
  321.     H1->left = x;
  322.     x->parent = NULL;
  323.     x->mark = 'F';
  324. }
  325.  
  326. /*
  327.  * Cascade Cutting in Fibonnaci Heap
  328.  */
  329. int FibonacciHeap::Cascase_cut(node* H1, node* y)
  330. {
  331.     node* z = y->parent;
  332.     if (z != NULL)
  333.     {
  334.         if (y->mark == 'F')
  335.         {
  336.             y->mark = 'T';
  337. 	}
  338.         else
  339.         {
  340.             Cut(H1, y, z);
  341.             Cascase_cut(H1, z);
  342.         }
  343.     }
  344. }
  345.  
  346. /*
  347.  * Find Nodes in Fibonnaci Heap
  348.  */
  349. node* FibonacciHeap::Find(node* H, int k)
  350. {
  351.     node* x = H;
  352.     x->C = 'Y';
  353.     node* p = NULL;
  354.     if (x->n == k)
  355.     {
  356.         p = x;
  357.         x->C = 'N';
  358.         return p;
  359.     }
  360.     if (p == NULL)
  361.     {
  362.         if (x->child != NULL )
  363.             p = Find(x->child, k);
  364.         if ((x->right)->C != 'Y' )
  365.             p = Find(x->right, k);
  366.     }
  367.     x->C = 'N';
  368.     return p;
  369. }
  370. /*
  371.  * Delete Nodes in Fibonnaci Heap
  372.  */
  373. int FibonacciHeap::Delete_key(node* H1, int k)
  374. {
  375.     node* np = NULL;
  376.     int t;
  377.     t = Decrease_key(H1, k, -5000);
  378.     if (!t)
  379.         np = Extract_Min(H);
  380.     if (np != NULL)
  381.         cout<<"Key Deleted"<<endl;
  382.     else
  383.         cout<<"Key not Deleted"<<endl;
  384.     return 0;
  385. }
  386. /*
  387.  * Main Contains Menu
  388.  */
  389. int main()
  390. {
  391.     int n, m, l;
  392.     FibonacciHeap fh;
  393.     node* p;
  394.     node* H;
  395.     H = fh.InitializeHeap();
  396.     while (1)
  397.     {
  398.         cout<<"----------------------------"<<endl;
  399.         cout<<"Operations on Binomial heap"<<endl;
  400.         cout<<"----------------------------"<<endl;
  401.         cout<<"1)Insert Element in the heap"<<endl;
  402.         cout<<"2)Extract Minimum key node"<<endl;
  403.         cout<<"3)Decrease key of a node"<<endl;
  404.         cout<<"4)Delete a node"<<endl;
  405.         cout<<"5)Display Heap"<<endl;
  406.         cout<<"6)Exit"<<endl;
  407.         cout<<"Enter Your Choice: ";
  408.         cin>>l;
  409.         switch(l)
  410.         {
  411.         case 1:
  412.             cout<<"Enter the element to be inserted: ";
  413.             cin>>m;
  414.             p = fh.Create_node(m);
  415.             H = fh.Insert(H, p);
  416.             break;
  417.         case 2:
  418.             p = fh.Extract_Min(H);
  419.             if (p != NULL)
  420.                 cout<<"The node with minimum key: "<<p->n<<endl;
  421.             else
  422.                 cout<<"Heap is empty"<<endl;
  423.             break;
  424.         case 3:
  425.             cout<<"Enter the key to be decreased: ";
  426.             cin>>m;
  427.             cout<<"Enter new key value: ";
  428.             cin>>l;
  429.             fh.Decrease_key(H, m, l);
  430.             break;
  431.         case 4:
  432.             cout<<"Enter the key to be deleted: ";
  433.             cin>>m;
  434.             fh.Delete_key(H, m);
  435.             break;
  436.         case 5:
  437.             cout<<"The Heap is: "<<endl;
  438.             fh.Display(H);
  439.             break;
  440.         case 6:
  441.             exit(1);
  442.         default:
  443.             cout<<"Wrong Choice"<<endl;
  444.         }
  445.     }
  446.     return 0;
  447. }

advertisement
$ g++ fibonnaciheap.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: 5
The Heap is: 
The root nodes of Heap are: 
5-->6-->7-->8-->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: 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: 3
Enter the key to be decreased: 3
Enter new key value: 1
Node not found in the Heap
----------------------------
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: 3
Enter the key to be decreased: 5
Enter new key value: 2
----------------------------
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: 2
----------------------------
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.

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.