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. }

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

advertisement
advertisement
advertisement
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn