C++ Program to Implement Heap

«
»
This C++ Program demonstrates the implementation of Heap.

Here is source code of the C++ Program to demonstrate 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 Heap
  3.  */
  4. #include <iostream>
  5. #include <cstdlib>
  6. #include <vector>
  7. #include <iterator>
  8. using namespace std;
  9. /*
  10.  * Class Declaration
  11.  */
  12. class Heap
  13. {
  14.     private:
  15.         vector <int> heap;
  16.         int left(int parent);
  17.         int right(int parent);
  18.         int parent(int child);
  19.         void heapifyup(int index);
  20.         void heapifydown(int index);
  21.     public:
  22.         Heap()
  23.         {}
  24.         void Insert(int element);
  25.         void DeleteMin();
  26.         int ExtractMin();
  27.         void DisplayHeap();
  28.         int Size();
  29. };
  30. /*
  31.  * Return Heap Size
  32.  */
  33. int Heap::Size()
  34. {
  35.     return heap.size();
  36. }
  37.  
  38. /*
  39.  * Insert Element into a Heap
  40.  */
  41. void Heap::Insert(int element)
  42. {
  43.     heap.push_back(element);
  44.     heapifyup(heap.size() -1);
  45. }
  46. /*
  47.  * Delete Minimum Element
  48.  */
  49. void Heap::DeleteMin()
  50. {
  51.     if (heap.size() == 0)
  52.     {
  53.         cout<<"Heap is Empty"<<endl;
  54.         return;
  55.     }
  56.     heap[0] = heap.at(heap.size() - 1);
  57.     heap.pop_back();
  58.     heapifydown(0);
  59.     cout<<"Element Deleted"<<endl;
  60. }
  61.  
  62. /*
  63.  * Extract Minimum Element
  64.  */
  65. int Heap::ExtractMin()
  66. {
  67.     if (heap.size() == 0)
  68.     {
  69.         return -1;
  70.     }
  71.     else
  72.         return heap.front();
  73. }
  74.  
  75. /*
  76.  * Display Heap
  77.  */
  78. void Heap::DisplayHeap()
  79. {
  80.     vector <int>::iterator pos = heap.begin();
  81.     cout<<"Heap -->  ";
  82.     while (pos != heap.end())
  83.     {
  84.         cout<<*pos<<" ";
  85.         pos++;
  86.     }
  87.     cout<<endl;
  88. }
  89.  
  90. /*
  91.  * Return Left Child
  92.  */
  93. int Heap::left(int parent)
  94. {
  95.     int l = 2 * parent + 1;
  96.     if(l < heap.size())
  97.         return l;
  98.     else
  99.         return -1;
  100. }
  101.  
  102. /*
  103.  * Return Right Child
  104.  */
  105. int Heap::right(int parent)
  106. {
  107.     int r = 2 * parent + 2;
  108.     if(r < heap.size())
  109.         return r;
  110.     else
  111.         return -1;
  112. }
  113.  
  114. /*
  115.  * Return Parent
  116.  */
  117. int Heap::parent(int child)
  118. {
  119.     int p = (child - 1)/2;
  120.     if(child == 0)
  121.         return -1;
  122.     else
  123.         return p;
  124. }
  125.  
  126. /*
  127.  * Heapify- Maintain Heap Structure bottom up
  128.  */
  129. void Heap::heapifyup(int in)
  130. {
  131.     if (in >= 0 && parent(in) >= 0 && heap[parent(in)] > heap[in])
  132.     {
  133.         int temp = heap[in];
  134.         heap[in] = heap[parent(in)];
  135.         heap[parent(in)] = temp;
  136.         heapifyup(parent(in));
  137.     }
  138. }
  139.  
  140. /*
  141.  * Heapify- Maintain Heap Structure top down
  142.  */
  143. void Heap::heapifydown(int in)
  144. {
  145.  
  146.     int child = left(in);
  147.     int child1 = right(in);
  148.     if (child >= 0 && child1 >= 0 && heap[child] > heap[child1])
  149.     {
  150.        child = child1;
  151.     }
  152.     if (child > 0)
  153.     {
  154.         int temp = heap[in];
  155.         heap[in] = heap[child];
  156.         heap[child] = temp;
  157.         heapifydown(child);
  158.     }
  159. }
  160.  
  161. /*
  162.  * Main Contains Menu
  163.  */
  164. int main()
  165. {
  166.     Heap h;
  167.     while (1)
  168.     {
  169.         cout<<"------------------"<<endl;
  170.         cout<<"Operations on Heap"<<endl;
  171.         cout<<"------------------"<<endl;
  172.         cout<<"1.Insert Element"<<endl;
  173.         cout<<"2.Delete Minimum Element"<<endl;
  174.         cout<<"3.Extract Minimum Element"<<endl;
  175.         cout<<"4.Print Heap"<<endl;
  176.         cout<<"5.Exit"<<endl;
  177.         int choice, element;
  178.         cout<<"Enter your choice: ";
  179.         cin>>choice;
  180.         switch(choice)
  181.         {
  182.         case 1:
  183.             cout<<"Enter the element to be inserted: ";
  184.             cin>>element;
  185.             h.Insert(element);
  186.             break;
  187.         case 2:
  188.             h.DeleteMin();
  189.             break;
  190.         case 3:
  191.             cout<<"Minimum Element: ";
  192.             if (h.ExtractMin() == -1)
  193.             {
  194.                 cout<<"Heap is Empty"<<endl;
  195.             }
  196.             else
  197.                 cout<<"Minimum Element:  "<<h.ExtractMin()<<endl;
  198.             break;
  199.         case 4:
  200.             cout<<"Displaying elements of Hwap:  ";
  201.             h.DisplayHeap();
  202.             break;
  203.         case 5:
  204.             exit(1);
  205.         default:
  206.             cout<<"Enter Correct Choice"<<endl;
  207.         }
  208.     }
  209.     return 0;
  210. }

advertisement
$ g++ heap.cpp
$ a.out
/*
------------------
Operations on Heap
------------------
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Print Heap
5.Exit
Enter your choice: 1
Enter the element to be inserted: 7
------------------
Operations on Heap
------------------
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Print Heap
5.Exit
Enter your choice: 4
Displaying elements of Hwap:  Heap -->  7
------------------
Operations on Heap
------------------
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Print Heap
5.Exit
Enter your choice: 1
Enter the element to be inserted: 4
------------------
Operations on Heap
------------------
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Print Heap
5.Exit
Enter your choice: 4
Displaying elements of Hwap:  Heap -->  4 7
------------------
Operations on Heap
------------------
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Print Heap
5.Exit
Enter your choice: 1
Enter the element to be inserted: 9
------------------
Operations on Heap
------------------
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Print Heap
5.Exit
Enter your choice: 4
Displaying elements of Hwap:  Heap -->  4 7 9
------------------
Operations on Heap
------------------
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Print Heap
5.Exit
Enter your choice: 1
Enter the element to be inserted: 3
------------------
Operations on Heap
------------------
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Print Heap
5.Exit
Enter your choice: 4
Displaying elements of Hwap:  Heap -->  3 4 9 7
------------------
Operations on Heap
------------------
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Print Heap
5.Exit
Enter your choice: 3
Minimum Element: Minimum Element:  3
------------------
Operations on Heap
------------------
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Print Heap
5.Exit
Enter your choice: 1
Enter the element to be inserted: 5
------------------
Operations on Heap
------------------
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Print Heap
5.Exit
Enter your choice: 4
Displaying elements of Hwap:  Heap -->  3 4 9 7 5
------------------
Operations on Heap
------------------
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Print Heap
5.Exit
Enter your choice: 1
Enter the element to be inserted: 11
------------------
Operations on Heap
------------------
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Print Heap
5.Exit
Enter your choice: 4
Displaying elements of Hwap:  Heap -->  3 4 9 7 5 11
------------------
Operations on Heap
------------------
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Print Heap
5.Exit
Enter your choice: 1
Enter the element to be inserted: 2
------------------
Operations on Heap
------------------
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Print Heap
5.Exit
Enter your choice: 4
Displaying elements of Hwap:  Heap -->  2 4 3 7 5 11 9
------------------
Operations on Heap
------------------
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Print Heap
5.Exit
Enter your choice: 2
Element Deleted
------------------
Operations on Heap
------------------
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Print Heap
5.Exit
Enter your choice: 4
Displaying elements of Hwap:  Heap -->  3 4 11 7 5 9
------------------
Operations on Heap
------------------
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Print Heap
5.Exit
Enter your choice: 3
Minimum Element: Minimum Element:  3
------------------
Operations on Heap
------------------
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Print Heap
5.Exit
Enter your choice: 2
Element Deleted
------------------
Operations on Heap
------------------
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Print Heap
5.Exit
Enter your choice: 4
Displaying elements of Hwap:  Heap -->  4 5 11 7 9
------------------
Operations on Heap
------------------
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Print Heap
5.Exit
Enter your choice: 3
Minimum Element: Minimum Element:  4
------------------
Operations on Heap
------------------
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Print Heap
5.Exit
Enter your choice: 5
 
------------------
(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
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