Code:
#include iostream
#include cstdlib
using namespace std;
/*
* 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;
}
/*
* Merging Skew Heaps
*/
Skew_Heap *merge(Skew_Heap *h1, Skew_Heap *h2)
{
Skew_Heap *temp;
if (h1 == NULL)
return h2;
else if (h2 == NULL)
return h1;
else
{
if (h1->key < h2->key)
{
temp = h1;
h1 = h2;
h2 = temp;
}
temp = h1->left;
h1->left = h1->right;
h1->right = temp;
h1->left = merge(h2, h1->left);
}
return h1;
}
/*
* Construct Skew Heap
*/
Skew_Heap *construct(Skew_Heap *root)
{
Skew_Heap *temp;
int input, val;
while (1)
{
cout<<"Enter the value of the node(0 to exit): ";
cin >> val;
if (val == 0)
break;
temp = new Skew_Heap;
temp->key = val;
root = merge(root, temp);
}
return root;
}
/*
* Insert into Skew Heap
*/
Skew_Heap *insert(Skew_Heap *root)
{
int val;
Skew_Heap *temp;
cout<<"Enter the value of the node: ";
cin >> val;
temp = new Skew_Heap;
temp->key = val;
root = merge(root, temp);
return root;
}
/*
* Delete Maximum from Skew Heap
*/
Skew_Heap *delete_max(Skew_Heap *root)
{
if (root == NULL)
{
cout << "The heap is empty"<
return NULL;
}
Skew_Heap *temp1, *temp2;
temp1 = root->left;
temp2 = root->right;
temp1 = merge(temp1, temp2);
cout << "Maximum Deleted "<
return temp1;
}
/*
* 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;
}
/*
* 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;
}
/*
* 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;
}
/*
* Display Skew Heap
*/
void print_heap(Skew_Heap *root)
{
cout << "Preorder traversal of the heap is " << endl;
preorder(root);
cout << endl;
cout << "Inorder traversal of the heap is " << endl;
inorder(root);
cout << endl;
cout << "Postorder traversal of the heap is " << endl;
postorder(root);
cout << endl;
}
};
/*
* Main Contains Menu
*/
int main()
{
Skew_Heap *head1, *temp1, *temp2, obj, *temp3;
int input;
head1 = NULL;
temp1 = NULL;
temp2 = NULL;
temp3 = NULL;
while(1)
{
cout << endl<< "-----------Operations on Skew Heap---------"<
cout << "1.Insert element into the heap"<
cout << "2.Delete maximum element from the heap"<
cout << "3.Merge two heaps"<
cout << "4.Print the heap"<
cout << "5.Print the maximum element of the heap"<
cout << "6.Merge the present heap with another heap"<
cout << "7.Exit"<
cout << "Enter your Choice: ";
cin >> input;
switch(input)
{
case 1:
head1 = obj.insert(head1);
break;
case 2:
head1 = obj.delete_max(head1);
break;
case 3:
cout << "Enter the first heap: "<
temp1 = obj.construct(temp1);
cout << "Enter the second heap: "<
temp2 = obj.construct(temp2);
temp1 = obj.merge(temp1, temp2);
cout << "The heap obtained after merging is: "<
obj.print_heap(temp1);
break;
case 4:
obj.print_heap(head1);
break;
case 5:
cout << "The maximum element existing in the heap is: ";
cout << head1->key << endl;
break;
case 6:
cout << "Enter the second heap"<
temp3 = obj.construct(temp3);
temp3 = obj.merge(temp3, head1);
cout << "The heap obtained after merging is: "<
obj.print_heap(temp3);
break;
case 7:
exit(1);
default:
cout<<"Enter Correct Choice"<
break;
}
}
return 0;
}
Output:
-----------Operations on Skew Heap---------
1.Insert element into the heap
2.Delete maximum element from the heap
3.Merge two heaps
4.Print the heap
5.Print the maximum element of the heap
6.Merge the present heap with another heap
7.Exit
Enter your Choice: 1
Enter the value of the node: 1
-----------Operations on Skew Heap---------
1.Insert element into the heap
2.Delete maximum element from the heap
3.Merge two heaps
4.Print the heap
5.Print the maximum element of the heap
6.Merge the present heap with another heap
7.Exit
Enter your Choice: 1
Enter the value of the node: 2
-----------Operations on Skew Heap---------
1.Insert element into the heap
2.Delete maximum element from the heap
3.Merge two heaps
4.Print the heap
5.Print the maximum element of the heap
6.Merge the present heap with another heap
7.Exit
Enter your Choice: 1
Enter the value of the node: 3
-----------Operations on Skew Heap---------
1.Insert element into the heap
2.Delete maximum element from the heap
3.Merge two heaps
4.Print the heap
5.Print the maximum element of the heap
6.Merge the present heap with another heap
7.Exit
Enter your Choice: 1
Enter the value of the node: 4
-----------Operations on Skew Heap---------
1.Insert element into the heap
2.Delete maximum element from the heap
3.Merge two heaps
4.Print the heap
5.Print the maximum element of the heap
6.Merge the present heap with another heap
7.Exit
Enter your Choice: 1
Enter the value of the node: 5
-----------Operations on Skew Heap---------
1.Insert element into the heap
2.Delete maximum element from the heap
3.Merge two heaps
4.Print the heap
5.Print the maximum element of the heap
6.Merge the present heap with another heap
7.Exit
Enter your Choice: 4
Preorder traversal of the heap is
5 4 3 2 1
Inorder traversal of the heap is
1 2 3 4 5
Postorder traversal of the heap is
1 2 3 4 5
-----------Operations on Skew Heap---------
1.Insert element into the heap
2.Delete maximum element from the heap
3.Merge two heaps
4.Print the heap
5.Print the maximum element of the heap
6.Merge the present heap with another heap
7.Exit
Enter your Choice: 5
The maximum element existing in the heap is: 5
-----------Operations on Skew Heap---------
1.Insert element into the heap
2.Delete maximum element from the heap
3.Merge two heaps
4.Print the heap
5.Print the maximum element of the heap
6.Merge the present heap with another heap
7.Exit
Enter your Choice: 2
Maximum Deleted
-----------Operations on Skew Heap---------
1.Insert element into the heap
2.Delete maximum element from the heap
3.Merge two heaps
4.Print the heap
5.Print the maximum element of the heap
6.Merge the present heap with another heap
7.Exit
Enter your Choice: 4
Preorder traversal of the heap is
4 3 2 1
Inorder traversal of the heap is
1 2 3 4
Postorder traversal of the heap is
1 2 3 4
-----------Operations on Skew Heap---------
1.Insert element into the heap
2.Delete maximum element from the heap
3.Merge two heaps
4.Print the heap
5.Print the maximum element of the heap
6.Merge the present heap with another heap
7.Exit
Enter your Choice: 5
The maximum element existing in the heap is: 4
-----------Operations on Skew Heap---------
1.Insert element into the heap
2.Delete maximum element from the heap
3.Merge two heaps
4.Print the heap
5.Print the maximum element of the heap
6.Merge the present heap with another heap
7.Exit
Enter your Choice: 3
Enter the first heap:
Enter the value of the node(0 to exit): 11
Enter the value of the node(0 to exit): 12
Enter the value of the node(0 to exit): 13
Enter the value of the node(0 to exit): 14
Enter the value of the node(0 to exit): 15
Enter the value of the node(0 to exit): 0
Enter the second heap:
Enter the value of the node(0 to exit): 16
Enter the value of the node(0 to exit): 17
Enter the value of the node(0 to exit): 18
Enter the value of the node(0 to exit): 19
Enter the value of the node(0 to exit): 20
Enter the value of the node(0 to exit): 0
The heap obtained after merging is:
Preorder traversal of the heap is
20 15 14 13 12 11 19 18 17 16
Inorder traversal of the heap is
11 12 13 14 15 20 16 17 18 19
Postorder traversal of the heap is
11 12 13 14 15 16 17 18 19 20
-----------Operations on Skew Heap---------
1.Insert element into the heap
2.Delete maximum element from the heap
3.Merge two heaps
4.Print the heap
5.Print the maximum element of the heap
6.Merge the present heap with another heap
7.Exit
Enter your Choice: 6
Enter the second heap
Enter the value of the node(0 to exit): 6
Enter the value of the node(0 to exit): 7
Enter the value of the node(0 to exit): 8
Enter the value of the node(0 to exit): 9
Enter the value of the node(0 to exit): 10
Enter the value of the node(0 to exit): 0
The heap obtained after merging is:
Preorder traversal of the heap is
10 4 3 2 1 9 8 7 6
Inorder traversal of the heap is
1 2 3 4 10 6 7 8 9
Postorder traversal of the heap is
1 2 3 4 6 7 8 9 10
-----------Operations on Skew Heap---------
1.Insert element into the heap
2.Delete maximum element from the heap
3.Merge two heaps
4.Print the heap
5.Print the maximum element of the heap
6.Merge the present heap with another heap
7.Exit
Enter your Choice: 7
------------------
(program exited with code: 1)
Press return to continue
More C++ Programs:
