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
If you wish to look at all C++ Programming examples, go to C++ Programs.

advertisement
advertisement
advertisement
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn