C++ Program to Implement Weak Heap

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

Here is source code of the C++ Program to demonstrate Weak 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 Weak Heap
  3.  */
  4. #include <iostream>
  5. #include <cstdlib>
  6. #include <vector>
  7. #include <algorithm>
  8. #include <iterator>
  9. #define GETFLAG(r, x) ((r[(x) >> 3] >> ((x) & 7)) & 1)
  10. #define TOGGLEFLAG(r, x) (r[(x) >> 3] ^= 1 << ((x) & 7))
  11. using namespace std;
  12. /*
  13.  * Class Declaration
  14.  */
  15. class WeakHeap
  16. {
  17.     private:
  18.         vector <int> wheap;
  19.     public:
  20.         WeakHeap()
  21.         {}
  22.         int Size();
  23.         void Insert(int element);
  24.         void DisplaySorted();
  25.         void WeakHeapMerge(unsigned char *r, int i, int j);
  26.         void WeakHeapSort();
  27. };
  28. /*
  29.  * Heap Size
  30.  */
  31. int WeakHeap::Size()
  32. {
  33.     return wheap.size();
  34. }
  35. /*
  36.  * Insert Element into a Heap
  37.  */
  38. void WeakHeap::Insert(int element)
  39. {
  40.     wheap.push_back(element);
  41.     WeakHeapSort();
  42. }
  43.  
  44. /*
  45.  * Merge Weak Heap
  46.  */
  47. void WeakHeap::WeakHeapMerge(unsigned char *r, int i, int j)
  48. {
  49.     if (wheap[i] < wheap[j])
  50.     {
  51.         TOGGLEFLAG(r, j);
  52.         swap(wheap[i], wheap[j]);
  53.     }
  54. }
  55. /*
  56.  * Weak Heap Sort
  57.  */
  58. void WeakHeap::WeakHeapSort()
  59. {
  60.     int n = Size();
  61.     if (n > 1)
  62.     {
  63.         int i, j, x, y, Gparent;
  64.         int s = (n + 7) / 8;
  65.         unsigned char * r = new unsigned char [s];
  66.         for (i = 0; i < n / 8; ++i)
  67.             r[i] = 0;
  68.         for (i = n - 1; i > 0; --i)
  69.         {
  70.             j = i;
  71.             while ((j & 1) == GETFLAG(r, j >> 1))
  72.                 j >>= 1;
  73.             Gparent = j >> 1;
  74.             WeakHeapMerge(r, Gparent, i);
  75.         }
  76.         for (i = n - 1; i >= 2; --i)
  77.         {
  78.             swap(wheap[0], wheap[i]);
  79.             x = 1;
  80.             while ((y = 2 * x + GETFLAG(r, x)) < i)
  81.                 x = y;
  82.             while (x > 0)
  83.             {
  84.                 WeakHeapMerge(r, 0, x);
  85.                 x >>= 1;
  86.             }
  87.         }
  88.         swap(wheap[0], wheap[1]);
  89.         delete[] r;
  90.     }
  91. }
  92. /*
  93.  * Display Sorted Heap
  94.  */
  95. void WeakHeap::DisplaySorted()
  96. {
  97.     vector <int>::iterator pos = wheap.begin();
  98.     cout<<"Heap -->  ";
  99.     while (pos != wheap.end())
  100.     {
  101.         cout<<*pos<<" ";
  102.         pos++;
  103.     }
  104.     cout<<endl;
  105. }
  106. /*
  107.  * Main Contains Menu
  108.  */
  109. int main()
  110. {
  111.     WeakHeap wh;
  112.     while (1)
  113.     {
  114.         cout<<"------------------"<<endl;
  115.         cout<<"Operations on Weak Heap"<<endl;
  116.         cout<<"------------------"<<endl;
  117.         cout<<"1.Insert Element"<<endl;
  118.         cout<<"2.Display Weak Heap Sorted Array"<<endl;
  119.         cout<<"3.Exit"<<endl;
  120.         int choice, element;
  121.         cout<<"Enter your choice: ";
  122.         cin>>choice;
  123.         switch(choice)
  124.         {
  125.         case 1:
  126.             cout<<"Enter the element to be inserted: ";
  127.             cin>>element;
  128.             wh.Insert(element);
  129.             break;
  130.         case 2:
  131.             cout<<"Array Sorted by Weak Heap:  ";
  132.             wh.DisplaySorted();
  133.             break;
  134.         case 3:
  135.             exit(1);
  136.         default:
  137.             cout<<"Enter Correct Choice"<<endl;
  138.         }
  139.     }
  140.     return 0;
  141. }

$ g++ weakheap.cpp
$ a.out
/*
------------------
Operations on Weak Heap
------------------
1.Insert Element
2.Display Weak Heap Sorted Array
3.Exit
Enter your choice: 1
Enter the element to be inserted: 5
------------------
Operations on Weak Heap
------------------
1.Insert Element
2.Display Weak Heap Sorted Array
3.Exit
Enter your choice: 1
Enter the element to be inserted: 4
------------------
Operations on Weak Heap
------------------
1.Insert Element
2.Display Weak Heap Sorted Array
3.Exit
Enter your choice: 2
Array Sorted by Weak Heap:  Heap -->  4 5
------------------
Operations on Weak Heap
------------------
1.Insert Element
2.Display Weak Heap Sorted Array
3.Exit
Enter your choice: 1
Enter the element to be inserted: 7
------------------
Operations on Weak Heap
------------------
1.Insert Element
2.Display Weak Heap Sorted Array
3.Exit
Enter your choice: 1
Enter the element to be inserted: 20
------------------
Operations on Weak Heap
------------------
1.Insert Element
2.Display Weak Heap Sorted Array
3.Exit
Enter your choice: 1
Enter the element to be inserted: 4
------------------
Operations on Weak Heap
------------------
1.Insert Element
2.Display Weak Heap Sorted Array
3.Exit
Enter your choice: 1
Enter the element to be inserted: 3
------------------
Operations on Weak Heap
------------------
1.Insert Element
2.Display Weak Heap Sorted Array
3.Exit
Enter your choice: 1
Enter the element to be inserted: 7
------------------
Operations on Weak Heap
------------------
1.Insert Element
2.Display Weak Heap Sorted Array
3.Exit
Enter your choice: 2
Array Sorted by Weak Heap:  Heap -->  3 4 4 5 7 7 20
------------------
Operations on Weak Heap
------------------
1.Insert Element
2.Display Weak Heap Sorted Array
3.Exit
Enter your choice: 1
Enter the element to be inserted: 11
------------------
Operations on Weak Heap
------------------
1.Insert Element
2.Display Weak Heap Sorted Array
3.Exit
Enter your choice: 2
Array Sorted by Weak Heap:  Heap -->  3 4 4 5 7 7 11 20
------------------
Operations on Weak Heap
------------------
1.Insert Element
2.Display Weak Heap Sorted Array
3.Exit
Enter your choice: 21
Enter Correct Choice
------------------
Operations on Weak Heap
------------------
1.Insert Element
2.Display Weak Heap Sorted Array
3.Exit
Enter your choice: 1
Enter the element to be inserted: 1
------------------
Operations on Weak Heap
------------------
1.Insert Element
2.Display Weak Heap Sorted Array
3.Exit
Enter your choice: 2
Array Sorted by Weak Heap:  Heap -->  1 3 4 4 5 7 7 11 20
------------------
Operations on Weak Heap
------------------
1.Insert Element
2.Display Weak Heap Sorted Array
3.Exit
Enter your choice: 3
 
------------------
(program exited with code: 0)
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.

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.