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
If you wish to look at all C++ Programming examples, go to C++ Programs.

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
I’m Manish - Founder and CTO at Sanfoundry. I’ve been working in tech for over 25 years, with deep focus on Linux kernel, SAN technologies, Advanced C, Full Stack and Scalable website designs.

You can connect with me on LinkedIn, watch my Youtube Masterclasses, or join my Telegram tech discussions.

If you’re in your 40s–60s and exploring new directions in your career, I also offer mentoring. Learn more here.