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

$ 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
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
I’m Manish - Founder and CTO at Sanfoundry. I’ve been working in tech for over 25 years, with deep focus on Linux kernel, SAN technologies, Advanced C, Full Stack and Scalable website designs.

You can connect with me on LinkedIn, watch my Youtube Masterclasses, or join my Telegram tech discussions.

If you’re in your 40s–60s and exploring new directions in your career, I also offer mentoring. Learn more here.