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.

```
/*
```
```
 * C++ Program to Implement Skew Heap
```
```
 */
```
```
#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"<<endl;

```
                return NULL;
```
```
            }
```
```
            Skew_Heap *temp1, *temp2;
```
```
            temp1 = root->left;
```
```
            temp2 = root->right;
```

            temp1 = merge(temp1, temp2);

            cout << "Maximum Deleted "<<endl;

```
            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---------"<<endl;

        cout << "1.Insert element into the heap"<<endl;

        cout << "2.Delete maximum element from the heap"<<endl;

        cout << "3.Merge two heaps"<<endl;

        cout << "4.Print the heap"<<endl;

        cout << "5.Print the maximum element of the heap"<<endl;

        cout << "6.Merge the present heap with another heap"<<endl;

```
        cout << "7.Exit"<<endl;
```
```
        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: "<<endl;

            temp1 = obj.construct(temp1);

            cout << "Enter the second heap: "<<endl;

            temp2 = obj.construct(temp2);

            temp1 = obj.merge(temp1, temp2);

            cout << "The heap obtained after merging is: "<<endl;

```
            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"<<endl;

            temp3 = obj.construct(temp3);

            temp3 = obj.merge(temp3, head1);

            cout << "The heap obtained after merging is: "<<endl;

```
            obj.print_heap(temp3);
```
```
            break;
```
```
        case 7:
```
```
            exit(1);
```
```
        default:
```

            cout<<"Enter Correct Choice"<<endl;

```
            break;
```
```
        }
```
```
    }
```
```
    return 0;
```
```
}
```

$ 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.

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

If you find any mistake above, kindly email to [email protected]

« Prev - C++ Program to Implement Pairing Heap

» Next - C++ Program to Implement Ternary Heap

Related Posts:

Check Data Structure Books
Practice Design & Analysis of Algorithms MCQ
Practice Programming MCQs
Check Programming Books
Apply for Computer Science Internship

Recommended Articles: