C++ Program to Implement Skew Heap

«
»
This C++ Program demonstrates the implementation of Skew Heap.

Here is source code of the C++ Program to demonstrate the implementation of Skew Heap. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. /*
  2.  * C++ Program to Implement Skew Heap
  3.  */
  4. #include <iostream>
  5. #include <cstdlib>
  6. using namespace std;
  7.  
  8. /*
  9.  * Skew Heap Class
  10.  */
  11. class Skew_Heap
  12. {
  13.     public:
  14.         int key;
  15.         Skew_Heap *right;
  16.         Skew_Heap *left;
  17.         Skew_Heap *parent;
  18.         /*
  19.          * Constructor
  20.          */
  21.         Skew_Heap()
  22.         {
  23.             key = 0;
  24.             right = NULL;
  25.             left = NULL;
  26.             parent = NULL;
  27.         }
  28.         /*
  29.          * Merging Skew Heaps
  30.          */
  31.         Skew_Heap *merge(Skew_Heap *h1, Skew_Heap *h2)
  32.         {
  33.             Skew_Heap *temp;
  34.             if (h1 == NULL)
  35.                 return h2;
  36.             else if (h2 == NULL)
  37.                 return h1;
  38.             else
  39.             {
  40.                 if (h1->key < h2->key)
  41.                 {
  42.                     temp = h1;
  43.                     h1 = h2;
  44.                     h2 = temp;
  45.                 }
  46.                 temp = h1->left;
  47.                 h1->left = h1->right;
  48.                 h1->right = temp;
  49.                 h1->left = merge(h2, h1->left);
  50.             }
  51.             return h1;
  52.         }
  53.         /*
  54.          * Construct Skew Heap
  55.          */
  56.         Skew_Heap *construct(Skew_Heap *root)
  57.         {
  58.             Skew_Heap *temp;
  59.             int input, val;
  60.             while (1)
  61.             {
  62.                 cout<<"Enter the value of the node(0 to exit): ";
  63.                 cin >> val;
  64.                 if (val == 0)
  65.                     break;
  66.                 temp = new Skew_Heap;
  67.                 temp->key = val;
  68.                 root = merge(root, temp);
  69.             }
  70.             return root;
  71.         }
  72.  
  73.         /*
  74.          * Insert into Skew Heap
  75.          */
  76.         Skew_Heap *insert(Skew_Heap *root)
  77.         {
  78.             int val;
  79.             Skew_Heap *temp;
  80.             cout<<"Enter the value of the node: ";
  81.             cin >> val;
  82.             temp = new Skew_Heap;
  83.             temp->key = val;
  84.             root = merge(root, temp);
  85.             return root;
  86.         }
  87.         /*
  88.          * Delete Maximum from Skew Heap
  89.          */
  90.         Skew_Heap *delete_max(Skew_Heap *root)
  91.         {
  92.             if (root == NULL)
  93.             {
  94.                 cout << "The heap is empty"<<endl;
  95.                 return NULL;
  96.             }
  97.             Skew_Heap *temp1, *temp2;
  98.             temp1 = root->left;
  99.             temp2 = root->right;
  100.             temp1 = merge(temp1, temp2);
  101.             cout << "Maximum Deleted "<<endl;
  102.             return temp1;
  103.         }
  104.         /*
  105.          * Preorder Traversal of Skew Heap
  106.          */
  107.         void preorder(Skew_Heap *root)
  108.         {
  109.             if (root == NULL)
  110.                 return;
  111.             else
  112.             {
  113.                 cout << root->key <<"  ";
  114.                 preorder(root->left);
  115.                 preorder(root->right);
  116.             }
  117.             return;
  118.         }
  119.         /*
  120.          * Inorder Traversal of Skew Heap
  121.          */
  122.         void inorder(Skew_Heap *root)
  123.         {
  124.             if (root == NULL)
  125.                 return;
  126.             else
  127.             {
  128.                 inorder(root->left);
  129.                 cout << root->key <<"  ";
  130.                 inorder(root->right);
  131.             }
  132.             return;
  133.         }
  134.         /*
  135.          * Postorder Traversal of Skew Heap
  136.          */
  137.         void postorder(Skew_Heap *root)
  138.         {
  139.             if (root == NULL)
  140.                 return;
  141.             else
  142.             {
  143.                 postorder(root->left);
  144.                 postorder(root->right);
  145.                 cout << root->key <<"   ";
  146.             }
  147.             return;
  148.         }
  149.         /*
  150.          * Display Skew Heap
  151.          */
  152.         void print_heap(Skew_Heap *root)
  153.         {
  154.             cout << "Preorder traversal of the heap is " << endl;
  155.             preorder(root);
  156.             cout << endl;
  157.             cout << "Inorder traversal of the heap is " << endl;
  158.             inorder(root);
  159.             cout << endl;
  160.             cout << "Postorder traversal of the heap is " << endl;
  161.             postorder(root);
  162.             cout << endl;
  163.         }
  164. };
  165. /*
  166.  * Main Contains Menu
  167.  */
  168. int main()
  169. {
  170.     Skew_Heap *head1, *temp1, *temp2, obj, *temp3;
  171.     int input;
  172.     head1 = NULL;
  173.     temp1 = NULL;
  174.     temp2 = NULL;
  175.     temp3 = NULL;
  176.     while(1)
  177.     {
  178.         cout << endl<< "-----------Operations on Skew Heap---------"<<endl;
  179.         cout << "1.Insert element into the heap"<<endl;
  180.         cout << "2.Delete maximum element from the heap"<<endl;
  181.         cout << "3.Merge two heaps"<<endl;
  182.         cout << "4.Print the heap"<<endl;
  183.         cout << "5.Print the maximum element of the heap"<<endl;
  184.         cout << "6.Merge the present heap with another heap"<<endl;
  185.         cout << "7.Exit"<<endl;
  186.         cout << "Enter your Choice: ";
  187.         cin >> input;
  188.         switch(input)
  189.         {
  190.         case 1:
  191.             head1 = obj.insert(head1);
  192.             break;
  193.         case 2:
  194.             head1 = obj.delete_max(head1);
  195.             break;
  196.         case 3:
  197.             cout << "Enter the first heap: "<<endl;
  198.             temp1 = obj.construct(temp1);
  199.             cout << "Enter the second heap: "<<endl;
  200.             temp2 = obj.construct(temp2);
  201.             temp1 = obj.merge(temp1, temp2);
  202.             cout << "The heap obtained after merging is: "<<endl;
  203.             obj.print_heap(temp1);
  204.             break;
  205.         case 4:
  206.             obj.print_heap(head1);
  207.             break;
  208.         case 5:
  209.             cout << "The maximum element existing in the heap is: ";
  210.             cout << head1->key << endl;
  211.             break;
  212.         case 6:
  213.             cout << "Enter the second heap"<<endl;
  214.             temp3 = obj.construct(temp3);
  215.             temp3 = obj.merge(temp3, head1);
  216.             cout << "The heap obtained after merging is: "<<endl;
  217.             obj.print_heap(temp3);
  218.             break;
  219.         case 7:
  220.             exit(1);
  221.         default:
  222.             cout<<"Enter Correct Choice"<<endl;
  223.             break;
  224.         }
  225.     }
  226.     return 0;
  227. }

advertisement
$ g++ skew_heap.cpp
$ a.out
 
 
-----------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

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

advertisement
If you wish to look at all C++ Programming examples, go to C++ Programs.

advertisement
advertisement
advertisement
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn