//BINOMIAL HEAP AND OPERATIONS ON IT//
#include<iostream.h>
struct node
{
int n;
int degree;
node* parent;
node* child;
node* sibling;
};
node* MAKE_BINOMIAL_HEAP();
int BINOMIAL_LINK(node*,node*);
node* CREATE_NODE(int);
node* BINOMIAL_HEAP_UNION(node*,node*);
node* BINOMIAL_HEAP_INSERT(node*,node*);
node* BINOMIAL_HEAP_MERGE(node*,node*);
node* BINOMIAL_HEAP_EXTRACT_MIN(node*);
int REVERT_LIST(node*);
int DISPLAY(node*);
node* H=MAKE_BINOMIAL_HEAP();
node* Hr=MAKE_BINOMIAL_HEAP();
node* FIND_NODE(node*,int);
int
BINOMIAL_HEAP_DECREASE_KEY(node*,int,int);
int BINOMIAL_HEAP_DELETE(node*,int);
int count=1;
int main()
{
int
n,m,l;
node* p;
char ch;
cout<<"\nENTER THE NUMBER OF
ELEMENTS:";
cin>>n;
cout<<"\nENTER THE
ELEMENTS:\n";
for(int i=1;i<=n;i++)
{
cin>>m;
node* np=CREATE_NODE(m);
H=BINOMIAL_HEAP_INSERT(H,np);
}
DISPLAY(H);
do
{
cout<<"\nENTER YOUR
CHOICES:-\n";
cout<<"\n >> 1)INSERT AN
ELEMENT\n >> 2)EXTRACT THE MINIMUM KEY NODE\n >>3)DECREASE A NODE
KEY\n >> 4)DELETE A NODE\n >> 5)EXIT\n";
cin>>l;
switch(l)
{
case 1:do{
cout<<"\nENTER THE ELEMENT TO BE
INSERTED:";
cin>>m;
p=CREATE_NODE(m);
H=BINOMIAL_HEAP_INSERT(H,p);
cout<<"\nNOW THE HEAP IS:\n";
DISPLAY(H);
cout<<"\nINSERT MORE??\n";
cin>>ch;
}
while(ch=='Y'||ch=='y');
break;
case 2:do{
cout<<"\nEXTRACTING THE MINIMUM KEY
NODE!!";
p=BINOMIAL_HEAP_EXTRACT_MIN(H);
if(p!=NULL)
cout<<"\nTHE EXTRACTED NODE IS
"<<p->n;
cout<<"\nNOW THE HEAP IS:\n";
DISPLAY(H);
cout<<"\nEXTRACT MORE??\n";
cin>>ch;
}
while(ch=='Y'||ch=='y');
break;
case 3:do{
cout<<"\nENTER THE KEY OF THE NODE
TO BE DECREASED:";
cin>>m;
cout<<"\nENTER THE NEW KEY
VALUE: ";
cin>>l;
BINOMIAL_HEAP_DECREASE_KEY(H,m,l);
cout<<"\nNOW THE HEAP IS:\n";
DISPLAY(H);
cout<<"\nDECREASE MORE??\n";
cin>>ch;
}while(ch=='Y'||ch=='y');
break;
case 4:do{
cout<<"\nENTER THE KEY TO BE
DELETED: ";
cin>>m;
BINOMIAL_HEAP_DELETE(H,m);
cout<<"\nDELETE MORE??\n";
cin>>ch;
}while(ch=='y'||ch=='Y');
break;
case 5:cout<<"\nGOOD
BYE!!!\n";
break;
default :cout<<"\nINVALID ENTRY!!!!TRY AGAIN!!!!\n";
}
}while(l!=5);
}
node* MAKE_BINOMIAL_HEAP()
{
node* np;
np=NULL;
return np;
}
int BINOMIAL_LINK(node* y,node* z)
{
y->parent=z;
y->sibling=z->child;
z->child=y;
z->degree=z->degree+1;
}
node* CREATE_NODE(int k)
{
node* p=new node;
p->n=k;
return p;
}
node* BINOMIAL_HEAP_INSERT(node* H,node* x)
{
node* H1=MAKE_BINOMIAL_HEAP();
x->parent=NULL;
x->child=NULL;
x->sibling=NULL;
x->degree=0;
H1=x;
H=BINOMIAL_HEAP_UNION(H,H1);
return H;
}
node* BINOMIAL_HEAP_UNION(node* H1,node*
H2)
{
node* H=MAKE_BINOMIAL_HEAP();
H=BINOMIAL_HEAP_MERGE(H1,H2);//the objects H1
H2 have not been freed
if(H==NULL)
return H;
node* prev_x;
node* next_x;
node* x;
prev_x=NULL;
x=H;
next_x=x->sibling;
while(next_x!=NULL)
{
if((x->degree!=next_x->degree)||((next_x->sibling!=NULL)&&(next_x->sibling)->degree==x->degree))
{
prev_x=x;
x=next_x;
}
else
{
if(x->n<=next_x->n)
{
x->sibling=next_x->sibling;
BINOMIAL_LINK(next_x,x);
}
else
{
if(prev_x==NULL)
H=next_x;
else
prev_x->sibling=next_x;
BINOMIAL_LINK(x,next_x);
x=next_x;
}
}
next_x=x->sibling;
}
return H;
}
node* BINOMIAL_HEAP_MERGE(node* H1,node* H2)
{
node* H=MAKE_BINOMIAL_HEAP();
node* y;
node* z;
node* a;
node* b;
y=H1;
z=H2;
if(y!=NULL)
{
if(z!=NULL&&y->degree<=z->degree)
H=y;
else
if(z!=NULL&&y->degree>z->degree)//need some modificationss
here;the first and the else conditions can be merged together!!!!
H=z;
else
H=y;
}
else
H=z;
while(y!=NULL&&z!=NULL)
{
if(y->degree<z->degree)
{
y=y->sibling;
}
else
if(y->degree==z->degree)
{
a=y->sibling;
y->sibling=z;
y=a;
}
else
{
b=z->sibling;
z->sibling=y;
z=b;
}
}
return H;
}
int
DISPLAY(node* H)
{
if(H==NULL)
{
cout<<"\nHEAP
EMPTY!!!";
return 0;
}
cout<<"\nTHE ROOT NODES ARE:-\n";
node* p;
p=H;
while(p!=NULL)
{
cout<<p->n;
if(p->sibling!=NULL)
cout<<"-->";p=p->sibling;
}
cout<<"\n";
}
node* BINOMIAL_HEAP_EXTRACT_MIN(node* H1)
{
Hr=NULL;
node* t=NULL;
node* x=H1;
if(x==NULL)
{
cout<<"\nNOTHING TO EXTRACT!!!!!!"<<endl;
return x;
}
int min=x->n;
node* p=x;
while(p->sibling!=NULL)
{
if((p->sibling)->n<min)
{
min=(p->sibling)->n;
t=p;
x=p->sibling;
}
p=p->sibling;
}
if(t==NULL&&x->sibling==NULL)
H1=NULL;
else if(t==NULL)
H1=x->sibling;
else if(t->sibling==NULL)
t=NULL;
else
t->sibling=x->sibling;
if(x->child!=NULL)
{
REVERT_LIST(x->child);
(x->child)->sibling=NULL;
}
H=BINOMIAL_HEAP_UNION(H1,Hr);
return x;
}
int REVERT_LIST(node* y)
{
if(y->sibling!=NULL)
{
REVERT_LIST(y->sibling);
(y->sibling)->sibling=y;
}
else
{
Hr=y;
}
}
node* FIND_NODE(node* H,int k)
{
node* x=H;
node* p=NULL;
if(x->n==k)
{
p=x;
return
p;
}
if(x->child!=NULL&&p==NULL)
{
p=FIND_NODE(x->child,k);
}
if(x->sibling!=NULL&&p==NULL)
{
p=FIND_NODE(x->sibling,k);
}
return p;
}
int BINOMIAL_HEAP_DECREASE_KEY(node* H,int
i,int k)
{
int temp;
node* p;
node* y;
node* z;
p=FIND_NODE(H,i);
if(p==NULL)
{
cout<<"\nINVALID
CHOICE OF KEY TO BE REDUCED!!!";
return
0;
}
if(k>p->n)
{
cout<<"\nERROR!!!!!THE NEW KEY IS GREATER THAN CURRENT
ONE!!!";
return 0;
}
p->n=k;
y=p;
z=p->parent;
while(z!=NULL&&y->n<z->n)
{
temp=y->n;
y->n=z->n;
z->n=temp;
y=z;
z=z->parent;
}
cout<<"\nKEY REDUCED SUCCESSFULLY!!!";
}
int BINOMIAL_HEAP_DELETE(node* H,int k)
{
node* np;
if(H==NULL)
{
cout<<"\nHEAP
EMPTY!!!!!";
return 0;
}
BINOMIAL_HEAP_DECREASE_KEY(H,k,-1000);
np=BINOMIAL_HEAP_EXTRACT_MIN(H);
if(np!=NULL)
cout<<"\nNODE DELETED
SUCCESSFULLY!!!";
}
No comments:
Post a Comment