C++ Program to Implement Binary Heap

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

Here is source code of the C++ Program to demonstrate Binary 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 Binary 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 BinaryHeap
  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.         BinaryHeap()
  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 BinaryHeap::Size()
  34. {
  35.     return heap.size();
  36. }
  37.  
  38. /*
  39.  * Insert Element into a Heap
  40.  */
  41. void BinaryHeap::Insert(int element)
  42. {
  43.     heap.push_back(element);
  44.     heapifyup(heap.size() -1);
  45. }
  46. /*
  47.  * Delete Minimum Element
  48.  */
  49. void BinaryHeap::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 BinaryHeap::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 BinaryHeap::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 BinaryHeap::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 BinaryHeap::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 BinaryHeap::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 BinaryHeap::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 BinaryHeap::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 && heap[in] > heap[child])
  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.     BinaryHeap 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
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