//IMPLEMENTATION OF SKEW HEAP IN CPP
.
DESCRIPTION-
A skew heap (or self-adjusting heap) is a heap data structure implemented as a binary tree. Skew heaps are advantageous because of their ability to merge more quickly than binary heaps.Also there is no structural constraints.
Two conditions must be satisfied:
1.The general heap order must be there i.e the root is minimum and same is true for its subtrees.
2.Every operation (insert, delete_min, merge) on two skew heaps must be done using a special skew heap merge.
MERGING:
Recursive Merge Process :
merge(h1, h2)
Let h1 and h2 be the two min skew heaps to be merged. Let h1%u2019s root be smaller than h2%u2019s root (If not smaller, we can swap to get the same).
We swap h1->left and h1->right.
h1->left = merge(h2, h1->left)
Example :
INSERTION:
To insert a single element:
1.build a heap containing just that one element
2.merge it into the existing heap
DELETION OF MINIMUM
To delete the minimum element:
1%u25CF take the left and right branches of the tree
2%u25CF these contain every element except the smallest
3%u25CF merge them
TRAVERSAL OF SKEW HEAP
There are many types of TRAVERSAL such as:
1. Preorder TRAVERSAL
~ It follows Root, Left child , Right child pathway
2.Inorder TRAVERSAL
~ It follows Left child,Root,Right child path
3.postorder TRAVERSAL
~ It follows Left child,Right child ,Root path
IMPLEMENTATION:-
In many functional languages, skew heaps become extremely simple to implement. Here is a complete sample implementation in dos.
// Coding:.
#include<iostream.h>
#include<stdlib.h>
class skew_heap
{
public:
int key;
skew_heap *right;
skew_heap *left;
skew_heap *parent;
skew_heap()
{
key=0;
right= NULL;
left= NULL;
parent= NULL;
}
skew_heap *merge(skew_heap *h1,skew_heap *h2)
{
skew_heap *tmp;
if(h1==NULL)
return h2;
else if(h2==NULL)
return h1;
else
{
if(h2->key < h1->key)
{
tmp=h1;
h1=h2;
h2=tmp;
}
tmp= h1->left;
h1->left = h1->right;
h1->right= tmp;
h1->left = merge(h2,h1->left);
return h1;
}
}
skew_heap *construct(skew_heap *root)
{
skew_heap *tmp;skew_heap obj;
int val;
while(1)
{
cout<<"\nENTER THE VALUE OF THE NODE AND ENTER '0' TO EXIT";
cin>>val;
if(val==0)
break;
tmp= new skew_heap;
tmp->key= val;
root=obj.merge(root,tmp);
}
return root;
}
skew_heap *insert(skew_heap *root)
{
int val;
skew_heap *tmp;
cout<<"\n ENTER THE VALUE OF THE NODE: ";
cin>>val;
tmp = new skew_heap;
tmp->key = val;
root = merge(root, tmp);
return root;
}
skew_heap *delete_min(skew_heap *root)
{
if(root==NULL)
{
cout<<"\n THE HEAP IS EMPTY";
return NULL;
}
skew_heap *tmp1,*tmp2;
tmp1= root->left;
tmp2= root->right;
tmp1= merge(tmp1,tmp2);
cout<<"\nMINIMUM DELETED "<<endl;
return tmp1;
}
void preorder(skew_heap *root)
{
if(root == NULL)
return;
else
{
cout<< root->key<<" ";
preorder(root->left);
preorder(root->right);
}
return;
}
void inorder(skew_heap *root)
{
if(root == NULL)
return;
else
{
inorder(root->left);
cout<< root->key<<" ";
inorder(root->right);
}
return;
}
void postorder(skew_heap *root)
{
if(root == NULL)
return;
else
{
postorder(root->left);
postorder(root->right);
cout<< root->key<<" ";
}
return;
}
void disp(skew_heap *root)
{
cout<< "\n PREORDER TRAVERSAL OF THE HEAP IS "<<endl;
preorder(root);
cout<<endl;
cout<< "\n INORDER TRAVERSAL OF THE HEAP IS "<<endl;
inorder(root);
cout<<endl;
cout<< "\n POSTORDER TRAVERSAL OF THE HEAP IS "<<endl;
postorder(root);
cout<<endl;
}
};
int main()
{
skew_heap *heap1,*temp1,*temp2,obj;
int choice;
heap1= NULL;
temp1= NULL;
temp2= NULL;
cout<<"\nCONSTUCT A SKEW HEAP: "<<endl;
heap1= obj.construct(heap1);
while(1)
{
cout<<endl<<"********OPERATIONS ON SKEW HEAP********"<<endl;
cout<<"1.INSERT ELEMENT INTO THE HEAP"<<endl;
cout<<"2.MERGE TWO HEAPS"<<endl;
cout<<"3.PRINT THE HEAP"<<endl;
cout<<"4.PRINT MINIMUM ELEMENT OF THE HEAP"<<endl;
cout<<"5.DELETE MINIMUM ELEMENT FROM THE HEAP"<<endl;
cout<<"6.EXIT"<<endl;
cout<<"ENTER YOUR CHOICE: ";
cin>> choice;
switch(choice)
{
case 1:
heap1=obj.insert(heap1);
break;
case 2:
cout<<"\n ENTER THE FIRST HEAP: "<<endl;
temp1= obj.construct(temp1);
cout<<"\n ENTER THE SECOND HEAP: "<<endl;
temp2= obj.construct(temp2);
temp1 = obj.merge(temp1 , temp2);
cout<<"\n THE HEAP OBTAINED AFTER MERGING IS: "<<endl;
obj.disp(temp1);
break;
case 3:
obj.disp(heap1);
break;
case 4:
obj.disp(heap1);
cout<<"\n THE MINIMUM ELEMENT EXISTING IN THE HEAP IS: ";
cout<<heap1->key <<endl;
break;
case 5:
heap1 = obj.delete_min(heap1);
break;
case 6:
exit(1);
default:
cout<<"\n pls enter correct choice"<<endl;
break;
}
}
}
~by N.Deepika
Comments