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
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 & technical discussions at Telegram SanfoundryClasses.