C++ Program to Implement Pairing Heap

This C++ Program demonstrates operations on Pairing Heap.

Here is source code of the C++ Program to demonstrate Pairing 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 Pairing Heap
  3.  */
  4. #include <iostream>
  5. #include <cstdlib>
  6. #include <vector>
  7. using namespace std;
  8. /*
  9.  * Node Class Declaration
  10.  */
  11. class PairNode
  12. {
  13.     public:
  14.         int element;
  15.         PairNode *leftChild;
  16.         PairNode *nextSibling;
  17.         PairNode *prev;
  18.         PairNode(int element)
  19.         {
  20.             this->element = element;
  21.             leftChild = NULL;
  22.             nextSibling = NULL;
  23.             prev = NULL;
  24.         }
  25. };
  26.  
  27. /*
  28.  * Class Declaration
  29.  */
  30. class PairingHeap
  31. {
  32.     private:
  33.         PairNode *root;
  34.         void reclaimMemory(PairNode *t);
  35.         void compareAndLink(PairNode * &first, PairNode *second);
  36.         PairNode *combineSiblings(PairNode *firstSibling);
  37.         PairNode *clone(PairNode *t);
  38.     public:
  39.         PairingHeap();
  40.         PairingHeap(PairingHeap &rhs);
  41.         ~PairingHeap();
  42.         bool isEmpty();
  43.         bool isFull();
  44.         int &findMin();
  45.         PairNode *Insert(int &x);
  46.         void deleteMin();
  47.         void deleteMin(int &minItem);
  48.         void makeEmpty();
  49.         void decreaseKey(PairNode *p, int &newVal );
  50.         PairingHeap &operator=(PairingHeap &rhs);
  51. };
  52.  
  53. PairingHeap::PairingHeap()
  54. {
  55.     root = NULL;
  56. }
  57.  
  58. PairingHeap::PairingHeap(PairingHeap & rhs)
  59. {
  60.     root = NULL;
  61.     *this = rhs;
  62. }
  63.  
  64. /*
  65.  * Destroy the leftist heap.
  66.  */
  67. PairingHeap::~PairingHeap()
  68. {
  69.     makeEmpty();
  70. }
  71.  
  72. /*
  73.  * Insert item x into the priority queue, maintaining heap order.
  74.  * Return a pointer to the node containing the new item.
  75.  */
  76. PairNode *PairingHeap::Insert(int &x)
  77. {
  78.     PairNode *newNode = new PairNode(x);
  79.     if (root == NULL)
  80.         root = newNode;
  81.     else
  82.         compareAndLink(root, newNode);
  83.     return newNode;
  84. }
  85.  
  86. /*
  87.  * Find the smallest item in the priority queue.
  88.  * Return the smallest item, or throw Underflow if empty.
  89.  */
  90. int &PairingHeap::findMin()
  91. {
  92.     return root->element;
  93. }
  94.  
  95. /*
  96.  * Remove the smallest item from the priority queue.
  97.  * Throws Underflow if empty.
  98.  */
  99. void PairingHeap::deleteMin()
  100. {
  101.     PairNode *oldRoot = root;
  102.     if (root->leftChild == NULL)
  103.         root = NULL;
  104.     else
  105.         root = combineSiblings(root->leftChild);
  106.     delete oldRoot;
  107. }
  108.  
  109. /*
  110.  * Remove the smallest item from the priority queue.
  111.  * Pass back the smallest item, or throw Underflow if empty.
  112.  */
  113. void PairingHeap::deleteMin(int &minItem)
  114. {
  115.     if (isEmpty())
  116.     {
  117.         cout<<"The Heap is Empty"<<endl;
  118.         return;
  119.     }
  120.     minItem = findMin();
  121.     deleteMin();
  122.     cout<<"Minimum Element: "<<minItem<<" deleted"<<endl;
  123. }
  124.  
  125. /*
  126.  * Test if the priority queue is logically empty.
  127.  * Returns true if empty, false otherwise.
  128.  */
  129. bool PairingHeap::isEmpty()
  130. {
  131.     return root == NULL;
  132. }
  133.  
  134. /*
  135.  * Test if the priority queue is logically full.
  136.  * Returns false in this implementation.
  137.  */
  138. bool PairingHeap::isFull()
  139. {
  140.     return false;
  141. }
  142.  
  143. /*
  144.  * Make the priority queue logically empty.
  145.  */
  146. void PairingHeap::makeEmpty()
  147. {
  148.     reclaimMemory(root);
  149.     root = NULL;
  150. }
  151.  
  152. /*
  153.  * Deep copy.
  154. */
  155. PairingHeap &PairingHeap::operator=(PairingHeap & rhs)
  156. {
  157.     if (this != &rhs)
  158.     {
  159.         makeEmpty( );
  160.         root = clone(rhs.root);
  161.     }
  162.     return *this;
  163. }
  164.  
  165. /*
  166.  * Internal method to make the tree empty.
  167.  */
  168. void PairingHeap::reclaimMemory(PairNode * t)
  169. {
  170.     if (t != NULL)
  171.     {
  172.         reclaimMemory(t->leftChild);
  173.         reclaimMemory(t->nextSibling);
  174.         delete t;
  175.     }
  176. }
  177.  
  178. /*
  179.  * Change the value of the item stored in the pairing heap.
  180.  * Does nothing if newVal is larger than currently stored value.
  181.  * p points to a node returned by insert.
  182.  * newVal is the new value, which must be smaller
  183.  *    than the currently stored value.
  184.  */
  185. void PairingHeap::decreaseKey(PairNode *p, int &newVal)
  186. {
  187.     if (p->element < newVal)
  188.         return;
  189.     p->element = newVal;
  190.     if (p != root)
  191.     {
  192.         if (p->nextSibling != NULL)
  193.             p->nextSibling->prev = p->prev;
  194.         if (p->prev->leftChild == p)
  195.             p->prev->leftChild = p->nextSibling;
  196.         else
  197.             p->prev->nextSibling = p->nextSibling;
  198.             p->nextSibling = NULL;
  199.             compareAndLink(root, p);
  200.     }
  201. }
  202.  
  203. /*
  204.  * Internal method that is the basic operation to maintain order.
  205.  * Links first and second together to satisfy heap order.
  206.  * first is root of tree 1, which may not be NULL.
  207.  *    first->nextSibling MUST be NULL on entry.
  208.  * second is root of tree 2, which may be NULL.
  209.  * first becomes the result of the tree merge.
  210.  */
  211. void PairingHeap::compareAndLink(PairNode * &first, PairNode *second)
  212. {
  213.     if (second == NULL)
  214.         return;
  215.     if (second->element < first->element)
  216.     {
  217.         second->prev = first->prev;
  218.         first->prev = second;
  219.         first->nextSibling = second->leftChild;
  220.         if (first->nextSibling != NULL)
  221.             first->nextSibling->prev = first;
  222.         second->leftChild = first;
  223.         first = second;
  224.     }
  225.     else
  226.     {
  227.         second->prev = first;
  228.         first->nextSibling = second->nextSibling;
  229.         if (first->nextSibling != NULL)
  230.             first->nextSibling->prev = first;
  231.         second->nextSibling = first->leftChild;
  232.         if (second->nextSibling != NULL)
  233.             second->nextSibling->prev = second;
  234.         first->leftChild = second;
  235.     }
  236. }
  237.  
  238. /*
  239.  * Internal method that implements two-pass merging.
  240.  * firstSibling the root of the conglomerate;
  241.  *     assumed not NULL.
  242.  */
  243. PairNode *PairingHeap::combineSiblings(PairNode *firstSibling)
  244. {
  245.     if (firstSibling->nextSibling == NULL)
  246.         return firstSibling;
  247.     static vector<PairNode *> treeArray(5);
  248.     int numSiblings = 0;
  249.     for (; firstSibling != NULL; numSiblings++)
  250.     {
  251.         if (numSiblings == treeArray.size())
  252.             treeArray.resize(numSiblings * 2);
  253.         treeArray[numSiblings] = firstSibling;
  254.         firstSibling->prev->nextSibling = NULL;
  255.         firstSibling = firstSibling->nextSibling;
  256.     }
  257.     if (numSiblings == treeArray.size())
  258.         treeArray.resize(numSiblings + 1);
  259.     treeArray[numSiblings] = NULL;
  260.     int i = 0;
  261.     for (; i + 1 < numSiblings; i += 2)
  262.         compareAndLink(treeArray[i], treeArray[i + 1]);
  263.     int j = i - 2;
  264.     if (j == numSiblings - 3)
  265.         compareAndLink (treeArray[j], treeArray[j + 2]);
  266.     for (; j >= 2; j -= 2)
  267.         compareAndLink(treeArray[j - 2], treeArray[j] );
  268.     return treeArray[0];
  269. }
  270.  
  271. /*
  272.  * Internal method to clone subtree.
  273.  */
  274. PairNode *PairingHeap::clone(PairNode * t)
  275. {
  276.     if (t == NULL)
  277.         return NULL;
  278.     else
  279.     {
  280.         PairNode *p = new PairNode(t->element);
  281.         if ((p->leftChild = clone( t->leftChild)) != NULL)
  282.             p->leftChild->prev = p;
  283.         if ((p->nextSibling = clone( t->nextSibling)) != NULL)
  284.             p->nextSibling->prev = p;
  285.         return p;
  286.     }
  287. }
  288.  
  289. /*
  290.  * Main Contains Menu
  291.  */
  292. int main()
  293. {
  294.     int choice, num, pos;
  295.     char ch;
  296.     PairingHeap h;
  297.     PairNode * pn;
  298.     while (1)
  299.     {
  300.         cout<<"-----------------"<<endl;
  301.         cout<<"Operations on Pairing Heap"<<endl;
  302.         cout<<"-----------------"<<endl;
  303.         cout<<"1.Insert Element and Decrease key"<<endl;
  304.         cout<<"2.Delete Minimum Element "<<endl;
  305.         cout<<"3.Quit"<<endl;
  306.         cout<<"Enter your choice : ";
  307.         cin>>choice;
  308.         switch(choice)
  309.         {
  310.         case 1:
  311.             cout<<"Enter the number to be inserted : ";
  312.             cin>>num;
  313.             pn = h.Insert(num);
  314.             cout<<"Want to decrease the key:(Y = Yes | N = No) ";
  315.             cin>>ch;
  316.             if (ch == 'Y')
  317.             {
  318.                 cout<<"Enter new key value: ";
  319.                 cin>>pos;
  320.                 h.decreaseKey(pn, pos);
  321.             }
  322.             break;
  323.         case 2:
  324.             h.deleteMin(num);
  325.             break;
  326.         case 3:
  327.             exit(1);
  328.         default:
  329.             cout<<"Wrong choice"<<endl;
  330.         }
  331.     }
  332.     return 0;
  333. }

$ g++ pairingheap.cpp
$ a.out
-----------------
Operations on Pairing Heap
-----------------
1.Insert Element and Decrease key
2.Delete Minimum Element 
3.Quit
Enter your choice : 1
Enter the number to be inserted : 100
Want to decrease the key:(Y = Yes | N = No) Y
Enter new key value: 50
-----------------
Operations on Pairing Heap
-----------------
1.Insert Element and Decrease key
2.Delete Minimum Element 
3.Quit
Enter your choice : 1
Enter the number to be inserted : 200
Want to decrease the key:(Y = Yes | N = No) N
-----------------
Operations on Pairing Heap
-----------------
1.Insert Element and Decrease key
2.Delete Minimum Element 
3.Quit
Enter your choice : 1
Enter the number to be inserted : 300
Want to decrease the key:(Y = Yes | N = No) N
-----------------
Operations on Pairing Heap
-----------------
1.Insert Element and Decrease key
2.Delete Minimum Element 
3.Quit
Enter your choice : 1
Enter the number to be inserted : 400
Want to decrease the key:(Y = Yes | N = No) N
-----------------
Operations on Pairing Heap
-----------------
1.Insert Element and Decrease key
2.Delete Minimum Element 
3.Quit
Enter your choice : 2
Minimum Element: 50 deleted
-----------------
Operations on Pairing Heap
-----------------
1.Insert Element and Decrease key
2.Delete Minimum Element 
3.Quit
Enter your choice : 1
Enter the number to be inserted : 75
Want to decrease the key:(Y = Yes | N = No) N
-----------------
Operations on Pairing Heap
-----------------
1.Insert Element and Decrease key
2.Delete Minimum Element 
3.Quit
Enter your choice : 2
Minimum Element: 75 deleted
-----------------
Operations on Pairing Heap
-----------------
1.Insert Element and Decrease key
2.Delete Minimum Element 
3.Quit
Enter your choice : 2
Minimum Element: 200 deleted
-----------------
Operations on Pairing Heap
-----------------
1.Insert Element and Decrease key
2.Delete Minimum Element 
3.Quit
Enter your choice : 2
Minimum Element: 300 deleted
-----------------
Operations on Pairing Heap
-----------------
1.Insert Element and Decrease key
2.Delete Minimum Element 
3.Quit
Enter your choice : 2
Minimum Element: 400 deleted
-----------------
Operations on Pairing Heap
-----------------
1.Insert Element and Decrease key
2.Delete Minimum Element 
3.Quit
Enter your choice : 2
The Heap is Empty
-----------------
Operations on Pairing Heap
-----------------
1.Insert Element and Decrease key
2.Delete Minimum Element 
3.Quit
Enter your choice : 3
 
------------------
(program exited with code: 1)
Press return to continue

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

advertisement
advertisement
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]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.