Code:
#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"<
return 0;
}
cout<<"The root nodes of Heap are: "<
do
{
cout<
p = p->right;
if (p != H)
{
cout<<"-->";
}
}
while (p != H && p->right != NULL);
cout<
}
/*
* 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;
Fibonnaci_link(H1, y, 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"<
return 0;
}
node* ptr = Find(H1, x);
if (ptr == NULL)
{
cout<<"Node not found in the Heap"<
return 1;
}
if (ptr->n < k)
{
cout<<"Entered key greater than current key"<
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"<
else
cout<<"Key not Deleted"<
return 0;
}
/*
* Main Contains Menu
*/
int main()
{
int n, m, l;
FibonacciHeap fh;
node* p;
node* H;
H = fh.InitializeHeap();
while (1)
{
cout<<"----------------------------"<
cout<<"Operations on Binomial heap"<
cout<<"----------------------------"<
cout<<"1)Insert Element in the heap"<
cout<<"2)Extract Minimum key node"<
cout<<"3)Decrease key of a node"<
cout<<"4)Delete a node"<
cout<<"5)Display Heap"<
cout<<"6)Exit"<
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: "<
else
cout<<"Heap is empty"<
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: "<
fh.Display(H);
break;
case 6:
exit(1);
default:
cout<<"Wrong Choice"<
}
}
return 0;
}
Output:
----------------------------
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
More C++ Programs:
