C++ Programming Code Examples

C++ > Data Structures Code Examples

C++ Program to Implement Pairing Heap

C++ Program to Implement Pairing Heap

This C++ Program demonstrates operations on Pairing Heap.

    #include <iostream>

    #include <cstdlib>

    #include <vector>

    using namespace std;

    /* Node Class Declaration     */

    class PairNode

    {

        public:

            int element;

            PairNode *leftChild;

            PairNode *nextSibling;

            PairNode *prev;

            PairNode(int element)

            {

                this->element = element;

                leftChild = NULL;

                nextSibling = NULL;

                prev = NULL;

            }

    };

    /* Class Declaration     */

    class PairingHeap

    {

        private:

            PairNode *root;

            void reclaimMemory(PairNode *t);

            void compareAndLink(PairNode * &first, PairNode *second);

            PairNode *combineSiblings(PairNode *firstSibling);

            PairNode *clone(PairNode *t);

        public:

            PairingHeap();

            PairingHeap(PairingHeap &rhs);

            ~PairingHeap();

            bool isEmpty();

            bool isFull();

            int &findMin();

            PairNode *Insert(int &x);

            void deleteMin();

            void deleteMin(int &minItem);

            void makeEmpty();

            void decreaseKey(PairNode *p, int &newVal );

            PairingHeap &operator=(PairingHeap &rhs);

    };

    PairingHeap::PairingHeap()

    {

        root = NULL;

    }

    PairingHeap::PairingHeap(PairingHeap & rhs)

    {

        root = NULL;

        *this = rhs;

    }

    /* Destroy the leftist heap.     */

    PairingHeap::~PairingHeap()

    {

        makeEmpty();

    }

    /* Insert item x into the priority queue, maintaining heap order. Return a pointer to the node containing the new item.     */

    PairNode *PairingHeap::Insert(int &x)

    {

        PairNode *newNode = new PairNode(x);

        if (root == NULL)

            root = newNode;

        else

            compareAndLink(root, newNode);

        return newNode;

    }

    /* Find the smallest item in the priority queue. Return the smallest item, or throw Underflow if empty.     */

    int &PairingHeap::findMin()

    {

        return root->element;

    }

    /* Remove the smallest item from the priority queue. Throws Underflow if empty.     */

    void PairingHeap::deleteMin()

    {

        PairNode *oldRoot = root;

        if (root->leftChild == NULL)

            root = NULL;

        else

            root = combineSiblings(root->leftChild);

        delete oldRoot;

    }

    /* Remove the smallest item from the priority queue. Pass back the smallest item, or throw Underflow if empty.     */

    void PairingHeap::deleteMin(int &minItem)

    {

        if (isEmpty())

        {

            cout<<"The Heap is Empty"<<endl;

            return;

        }

        minItem = findMin();

        deleteMin();

        cout<<"Minimum Element: "<<minItem<<" deleted"<<endl;

    }

    /* Test if the priority queue is logically empty.  Returns true if empty, false otherwise.     */

    bool PairingHeap::isEmpty()

    {

        return root == NULL;

    }

    /* Test if the priority queue is logically full. Returns false in this implementation.     */

    bool PairingHeap::isFull()

    {

        return false;

    }

    /* Make the priority queue logically empty.     */

    void PairingHeap::makeEmpty()

    {

        reclaimMemory(root);

        root = NULL;

    }

    /* Deep copy.    */

    PairingHeap &PairingHeap::operator=(PairingHeap & rhs)

    {

        if (this != &rhs)

        {

            makeEmpty( );

            root = clone(rhs.root);

        }

        return *this;

    }

    /* Internal method to make the tree empty.     */

    void PairingHeap::reclaimMemory(PairNode * t)

    {

        if (t != NULL)

        {

            reclaimMemory(t->leftChild);

            reclaimMemory(t->nextSibling);

            delete t;

        }

    }

    /* Change the value of the item stored in the pairing heap. Does nothing if newVal is larger than currently stored value. 
     * p points to a node returned by insert.
     * newVal is the new value, which must be smaller than the currently stored value.     */

    void PairingHeap::decreaseKey(PairNode *p, int &newVal)

    {

        if (p->element < newVal)

            return;

        p->element = newVal;

        if (p != root)

        {

            if (p->nextSibling != NULL)

                p->nextSibling->prev = p->prev;

            if (p->prev->leftChild == p)

                p->prev->leftChild = p->nextSibling;

            else

                p->prev->nextSibling = p->nextSibling;

                p->nextSibling = NULL;

                compareAndLink(root, p);

        }

    }

    /* Internal method that is the basic operation to maintain order.

     * Links first and second together to satisfy heap order.

     * first is root of tree 1, which may not be NULL.

     *    first->nextSibling MUST be NULL on entry.

     * second is root of tree 2, which may be NULL.

     * first becomes the result of the tree merge.    */

    void PairingHeap::compareAndLink(PairNode * &first, PairNode *second)

    {

        if (second == NULL)

            return;

        if (second->element < first->element)

        {

            second->prev = first->prev;

            first->prev = second;

            first->nextSibling = second->leftChild;

            if (first->nextSibling != NULL)

                first->nextSibling->prev = first;

            second->leftChild = first;

            first = second;

        }

        else

        {

            second->prev = first;

            first->nextSibling = second->nextSibling;

            if (first->nextSibling != NULL)

                first->nextSibling->prev = first;

            second->nextSibling = first->leftChild;

            if (second->nextSibling != NULL)

                second->nextSibling->prev = second;

            first->leftChild = second;

        }

    }

    /* Internal method that implements two-pass merging.

     * firstSibling the root of the conglomerate;

     *     assumed not NULL.     */

    PairNode *PairingHeap::combineSiblings(PairNode *firstSibling)

    {

        if (firstSibling->nextSibling == NULL)

            return firstSibling;

        static vector<PairNode *> treeArray(5);

        int numSiblings = 0;

        for (; firstSibling != NULL; numSiblings++)

        {

            if (numSiblings == treeArray.size())

                treeArray.resize(numSiblings * 2);

            treeArray[numSiblings] = firstSibling;

            firstSibling->prev->nextSibling = NULL;

            firstSibling = firstSibling->nextSibling;

        }

        if (numSiblings == treeArray.size())

            treeArray.resize(numSiblings + 1);

        treeArray[numSiblings] = NULL;

        int i = 0;

        for (; i + 1 < numSiblings; i += 2)

            compareAndLink(treeArray[i], treeArray[i + 1]);

        int j = i - 2;

        if (j == numSiblings - 3)

            compareAndLink (treeArray[j], treeArray[j + 2]);

        for (; j >= 2; j -= 2)

            compareAndLink(treeArray[j - 2], treeArray[j] );

        return treeArray[0];

    }

    /* Internal method to clone subtree.     */

    PairNode *PairingHeap::clone(PairNode * t)

    {

        if (t == NULL)

            return NULL;

        else

        {

            PairNode *p = new PairNode(t->element);

            if ((p->leftChild = clone( t->leftChild)) != NULL)

                p->leftChild->prev = p;

            if ((p->nextSibling = clone( t->nextSibling)) != NULL)

                p->nextSibling->prev = p;

            return p;

        }

    }

    /* Main Contains Menu     */

    int main()

    {

        int choice, num, pos;

        char ch;

        PairingHeap h;

        PairNode * pn;

        while (1)

        {

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

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

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

            cout<<"1.Insert Element and Decrease key"<<endl;

            cout<<"2.Delete Minimum Element "<<endl;

            cout<<"3.Quit"<<endl;

            cout<<"Enter your choice : ";

            cin>>choice;

            switch(choice)

            {

            case 1:

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

                cin>>num;

                pn = h.Insert(num);

                cout<<"Want to decrease the key:(Y = Yes | N = No) ";

                cin>>ch;

                if (ch == 'Y')

                {

                    cout<<"Enter new key value: ";

                    cin>>pos;

                    h.decreaseKey(pn, pos);

                }

                break;

            case 2:

                h.deleteMin(num);

                break;

            case 3:

                exit(1);

            default:

                cout<<"Wrong choice"<<endl;

            }

        }

        return 0;

    }