IMPLEMENTATION OF SKEW HEAP IN CPP














































IMPLEMENTATION OF SKEW HEAP IN CPP



//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:.            

/* C++ PROGRAM TO IMPLEMENT SKEW HEAPS made by:- N.DEEPIKA*/ #include<iostream.h> #include<stdlib.h> //skew heap class class skew_heap { public: int key; skew_heap *right; skew_heap *left; skew_heap *parent; // *constructor* skew_heap() { key=0; right= NULL; left= NULL; parent= NULL; } /*function to merge skew heaps*/ 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; } } //function to construct skew heap 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; } //function to insert into skew heap 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; } //function to delete min value from the skew heap 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; } /* TRAVERSALS OF SKEW HEAP: *PREORDER *INORDER *POSTORDER */ //Function for Preorder traversal of skew heap void preorder(skew_heap *root) { if(root == NULL) return; else { cout<< root->key<<" "; preorder(root->left); preorder(root->right); } return; } //Function for inorder traversal of skew heap void inorder(skew_heap *root) { if(root == NULL) return; else { inorder(root->left); cout<< root->key<<" "; inorder(root->right); } return; } //Function for postorder traversal of skew heap void postorder(skew_heap *root) { if(root == NULL) return; else { postorder(root->left); postorder(root->right); cout<< root->key<<" "; } return; } //FUNCTION TO DISPLAY THE SKEW HEAP 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; } }; // main function 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

OUTPUT:


Comments