C++ Programming Code Examples

C++ > Data Structures Code Examples

C++ Program to Implement Weak Heap



C++ Program to Implement Weak Heap

This C++ Program demonstrates the implementation of Weak heap.

    #include <iostream>

    #include <cstdlib>

    #include <vector>

    #include <algorithm>

    #include <iterator>

    #define GETFLAG(r, x) ((r[(x) >> 3] >> ((x) & 7)) & 1)

    #define TOGGLEFLAG(r, x) (r[(x) >> 3] ^= 1 << ((x) & 7))

    using namespace std;

    /* Class Declaration     */

    class WeakHeap

    {

        private:

            vector <int> wheap;

        public:

            WeakHeap()

            {}

            int Size();

            void Insert(int element);

            void DisplaySorted();

            void WeakHeapMerge(unsigned char *r, int i, int j);

            void WeakHeapSort();

    };

    /* Heap Size     */

    int WeakHeap::Size()

    {

        return wheap.size();

    }

    /* Insert Element into a Heap     */

    void WeakHeap::Insert(int element)

    {

        wheap.push_back(element);

        WeakHeapSort();

    }

    /* Merge Weak Heap     */

    void WeakHeap::WeakHeapMerge(unsigned char *r, int i, int j)

    {

        if (wheap[i] < wheap[j])

        {

            TOGGLEFLAG(r, j);

            swap(wheap[i], wheap[j]);

        }

    }

    /* Weak Heap Sort     */

    void WeakHeap::WeakHeapSort()

    {

        int n = Size();

        if (n > 1)

        {

            int i, j, x, y, Gparent;

            int s = (n + 7) / 8;

            unsigned char * r = new unsigned char [s];

            for (i = 0; i < n / 8; ++i)

                r[i] = 0;

            for (i = n - 1; i > 0; --i)

            {

                j = i;

                while ((j & 1) == GETFLAG(r, j >> 1))

                    j >>= 1;

                Gparent = j >> 1;

                WeakHeapMerge(r, Gparent, i);

            }

            for (i = n - 1; i >= 2; --i)

            {

                swap(wheap[0], wheap[i]);

                x = 1;

                while ((y = 2 * x + GETFLAG(r, x)) < i)

                    x = y;

                while (x > 0)

                {

                    WeakHeapMerge(r, 0, x);

                    x >>= 1;

                }

            }

            swap(wheap[0], wheap[1]);

            delete[] r;

        }

    }

    /* Display Sorted Heap     */

    void WeakHeap::DisplaySorted()

    {

        vector <int>::iterator pos = wheap.begin();

        cout<<"Heap -->  ";

        while (pos != wheap.end())

        {

            cout<<*pos<<" ";

            pos++;

        }

        cout<<endl;

    }

    /* Main Contains Menu     */

    int main()

    {

        WeakHeap wh;

        while (1)

        {

            cout<<"------------------"<<endl;

            cout<<"Operations on Weak Heap"<<endl;

            cout<<"------------------"<<endl;

            cout<<"1.Insert Element"<<endl;

            cout<<"2.Display Weak Heap Sorted Array"<<endl;

            cout<<"3.Exit"<<endl;

            int choice, element;

            cout<<"Enter your choice: ";

            cin>>choice;

            switch(choice)

            {

            case 1:

                cout<<"Enter the element to be inserted: ";

                cin>>element;

                wh.Insert(element);

                break;

            case 2:

                cout<<"Array Sorted by Weak Heap:  ";

                wh.DisplaySorted();

                break;

            case 3:

                exit(1);

            default:

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

            }

        }

        return 0;

    }