# C++ Program to Implement Fibonacci Heap

We saw a lot of information in the previous article. We are going to know about this very clearly in the article C++ Program to Implement Fibonacci Heap. I think you will like this article very much. Let’s go into the article.

## C++ Program to Implement Fibonacci Heap

``````#include <iostream>

#include <cmath>

#include <cstdlib>

using namespace std;

/* Node Declaration     */

struct node

{

int n;

int degree;

node* parent;

node* child;

node* left;

node* right;

char mark;

char C;

};

/* Class Declaration     */

class FibonacciHeap

{

private:

int nH;

node *H;

public:

node* InitializeHeap();

int Fibonnaci_link(node*, node*, node*);

node *Create_node(int);

node *Insert(node *, node *);

node *Union(node *, node *);

node *Extract_Min(node *);

int Consolidate(node *);

int Display(node *);

node *Find(node *, int);

int Decrease_key(node *, int, int);

int Delete_key(node *,int);

int Cut(node *, node *, node *);

int Cascase_cut(node *, node *);

FibonacciHeap()

{

H = InitializeHeap();

}

};

/* Initialize Heap     */

node* FibonacciHeap::InitializeHeap()

{

node* np;

np = NULL;

return np;

}

/* Create Node     */

node* FibonacciHeap::Create_node(int value)

{

node* x = new node;

x->n = value;

return x;

}

/* Insert Node     */

node* FibonacciHeap::Insert(node* H, node* x)

{

x->degree = 0;

x->parent = NULL;

x->child = NULL;

x->left = x;

x->right = x;

x->mark = 'F';

x->C = 'N';

if (H != NULL)

{

(H->left)->right = x;

x->right = H;

x->left = H->left;

H->left = x;

if (x->n < H->n)

H = x;

}

else

{

H = x;

}

nH = nH + 1;

return H;

}

/* Link Nodes in Fibonnaci Heap     */

int FibonacciHeap::Fibonnaci_link(node* H1, node* y, node* z)

{

(y->left)->right = y->right;

(y->right)->left = y->left;

if (z->right == z)

H1 = z;

y->left = y;

y->right = y;

y->parent = z;

if (z->child == NULL)

z->child = y;

y->right = z->child;

y->left = (z->child)->left;

((z->child)->left)->right = y;

(z->child)->left = y;

if (y->n < (z->child)->n)

z->child = y;

z->degree++;

}

/* Union Nodes in Fibonnaci Heap     */

node* FibonacciHeap::Union(node* H1, node* H2)

{

node* np;

node* H = InitializeHeap();

H = H1;

(H->left)->right = H2;

(H2->left)->right = H;

np = H->left;

H->left = H2->left;

H2->left = np;

return H;

}

/* Display Fibonnaci Heap     */

int FibonacciHeap::Display(node* H)

{

node* p = H;

if (p == NULL)

{

cout<<"The Heap is Empty"<<endl;

return 0;

}

cout<<"The root nodes of Heap are: "<<endl;

do

{

cout<<p->n;

p = p->right;

if (p != H)

{

cout<<"-->";

}

}

while (p != H && p->right != NULL);

cout<<endl;

}

/* Extract Min Node in Fibonnaci Heap     */

node* FibonacciHeap::Extract_Min(node* H1)

{

node* p;

node* ptr;

node* z = H1;

p = z;

ptr = z;

if (z == NULL)

return z;

node* x;

node* np;

x = NULL;

if (z->child != NULL)

x = z->child;

if (x != NULL)

{

ptr = x;

do

{

np = x->right;

(H1->left)->right = x;

x->right = H1;

x->left = H1->left;

H1->left = x;

if (x->n < H1->n)

H1 = x;

x->parent = NULL;

x = np;

}

while (np != ptr);

}

(z->left)->right = z->right;

(z->right)->left = z->left;

H1 = z->right;

if (z == z->right && z->child == NULL)

H = NULL;

else

{

H1 = z->right;

Consolidate(H1);

}

nH = nH - 1;

return p;

}

/* Consolidate Node in Fibonnaci Heap     */

int FibonacciHeap::Consolidate(node* H1)

{

int d, i;

float f = (log(nH)) / (log(2));

int D = f;

node* A[D];

for (i = 0; i <= D; i++)

A[i] = NULL;

node* x = H1;

node* y;

node* np;

node* pt = x;

do

{

pt = pt->right;

d = x->degree;

while (A[d] != NULL)

{

y = A[d];

if (x->n > y->n)

{

np = x;

x = y;

y = np;

}

if (y == H1)

H1 = x;

if (x->right == x)

H1 = x;

A[d] = NULL;

d = d + 1;

}

A[d] = x;

x = x->right;

}

while (x != H1);

H = NULL;

for (int j = 0; j <= D; j++)

{

if (A[j] != NULL)

{

A[j]->left = A[j];

A[j]->right =A[j];

if (H != NULL)

{

(H->left)->right = A[j];

A[j]->right = H;

A[j]->left = H->left;

H->left = A[j];

if (A[j]->n < H->n)

H = A[j];

}

else

{

H = A[j];

}

if(H == NULL)

H = A[j];

else if (A[j]->n < H->n)

H = A[j];

}

}

}

/* Decrease key of Nodes in Fibonnaci Heap     */

int FibonacciHeap::Decrease_key(node*H1, int x, int k)

{

node* y;

if (H1 == NULL)

{

cout<<"The Heap is Empty"<<endl;

return 0;

}

node* ptr = Find(H1, x);

if (ptr == NULL)

{

return 1;

}

if (ptr->n < k)

{

cout<<"Entered key greater than current key"<<endl;

return 0;

}

ptr->n = k;

y = ptr->parent;

if (y != NULL && ptr->n < y->n)

{

Cut(H1, ptr, y);

Cascase_cut(H1, y);

}

if (ptr->n < H->n)

H = ptr;

return 0;

}

/* Cut Nodes in Fibonnaci Heap     */

int FibonacciHeap::Cut(node* H1, node* x, node* y)

{

if (x == x->right)

y->child = NULL;

(x->left)->right = x->right;

(x->right)->left = x->left;

if (x == y->child)

y->child = x->right;

y->degree = y->degree - 1;

x->right = x;

x->left = x;

(H1->left)->right = x;

x->right = H1;

x->left = H1->left;

H1->left = x;

x->parent = NULL;

x->mark = 'F';

}

/* Cascade Cutting in Fibonnaci Heap     */

int FibonacciHeap::Cascase_cut(node* H1, node* y)

{

node* z = y->parent;

if (z != NULL)

{

if (y->mark == 'F')

{

y->mark = 'T';

}

else

{

Cut(H1, y, z);

Cascase_cut(H1, z);

}

}

}

/* Find Nodes in Fibonnaci Heap     */

node* FibonacciHeap::Find(node* H, int k)

{

node* x = H;

x->C = 'Y';

node* p = NULL;

if (x->n == k)

{

p = x;

x->C = 'N';

return p;

}

if (p == NULL)

{

if (x->child != NULL )

p = Find(x->child, k);

if ((x->right)->C != 'Y' )

p = Find(x->right, k);

}

x->C = 'N';

return p;

}

/* Delete Nodes in Fibonnaci Heap     */

int FibonacciHeap::Delete_key(node* H1, int k)

{

node* np = NULL;

int t;

t = Decrease_key(H1, k, -5000);

if (!t)

np = Extract_Min(H);

if (np != NULL)

cout<<"Key Deleted"<<endl;

else

cout<<"Key not Deleted"<<endl;

return 0;

}

/* Main Contains Menu     */

int main()

{

int n, m, l;

FibonacciHeap fh;

node* p;

node* H;

H = fh.InitializeHeap();

while (1)

{

cout<<"----------------------------"<<endl;

cout<<"Operations on Binomial heap"<<endl;

cout<<"----------------------------"<<endl;

cout<<"1)Insert Element in the heap"<<endl;

cout<<"2)Extract Minimum key node"<<endl;

cout<<"3)Decrease key of a node"<<endl;

cout<<"4)Delete a node"<<endl;

cout<<"5)Display Heap"<<endl;

cout<<"6)Exit"<<endl;

cout<<"Enter Your Choice: ";

cin>>l;

switch(l)

{

case 1:

cout<<"Enter the element to be inserted: ";

cin>>m;

p = fh.Create_node(m);

H = fh.Insert(H, p);

break;

case 2:

p = fh.Extract_Min(H);

if (p != NULL)

cout<<"The node with minimum key: "<<p->n<<endl;

else

cout<<"Heap is empty"<<endl;

break;

case 3:

cout<<"Enter the key to be decreased: ";

cin>>m;

cout<<"Enter new key value: ";

cin>>l;

fh.Decrease_key(H, m, l);

break;

case 4:

cout<<"Enter the key to be deleted: ";

cin>>m;

fh.Delete_key(H, m);

break;

case 5:

cout<<"The Heap is: "<<endl;

fh.Display(H);

break;

case 6:

exit(1);

default:

cout<<"Wrong Choice"<<endl;

}

}

return 0;

}``````

## Final Words

C++ Program to Implement Fibonacci Heap This article is your favorite topic because it is your favorite. And I will meet you in the next article.

Hi, I'm Ranjith a full-time Blogger, YouTuber, Affiliate Marketer, & founder of Coding Deekshi. Here, I post about programming to help developers.

Share on: