Here is the source code of the program to implement heap C++ programming language.
#include <iostream> #include <cstdlib> #include <vector> #include <iterator> using namespace std; // Class Declaration class Heap { private: vector <int> heap; int left(int parent); int right(int parent); int parent(int child); void heapifyup(int index); void heapifydown(int index); public: Heap() {} void Insert(int element); void DeleteMin(); int ExtractMin(); void DisplayHeap(); int Size(); }; // Return Heap Size int Heap::Size() { return heap.size(); } // Insert Element into a Heap void Heap::Insert(int element) { heap.push_back(element); heapifyup(heap.size() -1); } // Delete Minimum Element void Heap::DeleteMin() { if (heap.size() == 0) { cout<<"Heap is Empty"<<endl; return; } heap[0] = heap.at(heap.size() - 1); heap.pop_back(); heapifydown(0); cout<<"Element Deleted"<<endl; } // Extract Minimum Element int Heap::ExtractMin() { if (heap.size() == 0) { return -1; } else return heap.front(); } // Display Heap void Heap::DisplayHeap() { vector <int>::iterator pos = heap.begin(); cout<<"Heap --> "; while (pos != heap.end()) { cout<<*pos<<" "; pos++; } cout<<endl; } // Return Left Child int Heap::left(int parent) { int l = 2 * parent + 1; if(l < heap.size()) return l; else return -1; } // Return Right Child int Heap::right(int parent) { int r = 2 * parent + 2; if(r < heap.size()) return r; else return -1; } // Return Parent int Heap::parent(int child) { int p = (child - 1)/2; if(child == 0) return -1; else return p; } // Heapify- Maintain Heap Structure bottom up void Heap::heapifyup(int in) { if (in >= 0 && parent(in) >= 0 && heap[parent(in)] > heap[in]) { int temp = heap[in]; heap[in] = heap[parent(in)]; heap[parent(in)] = temp; heapifyup(parent(in)); } } // Heapify- Maintain Heap Structure top down void Heap::heapifydown(int in) { int child = left(in); int child1 = right(in); if (child >= 0 && child1 >= 0 && heap[child] > heap[child1]) { child = child1; } if (child > 0) { int temp = heap[in]; heap[in] = heap[child]; heap[child] = temp; heapifydown(child); } } // Main Contains Menu int main() { Heap h; while (1) { cout<<"------------------"<<endl; cout<<"Operations on Heap"<<endl; cout<<"------------------"<<endl; cout<<"1.Insert Element"<<endl; cout<<"2.Delete Minimum Element"<<endl; cout<<"3.Extract Minimum Element"<<endl; cout<<"4.Print Heap"<<endl; cout<<"5.Exit"<<endl; int choice, element; cout<<"Enter your choice: "; cin>>choice; switch(choice) { case 1: cout<<"Enter the element to be inserted: "; cin>>element; h.Insert(element); break; case 2: h.DeleteMin(); break; case 3: cout<<"Minimum Element: "; if (h.ExtractMin() == -1) { cout<<"Heap is Empty"<<endl; } else cout<<"Minimum Element: "<<h.ExtractMin()<<endl; break; case 4: cout<<"Displaying elements of Hwap: "; h.DisplayHeap(); break; case 5: exit(1); default: cout<<"Enter Correct Choice"<<endl; } } return 0; }
Sample Output:
------------------ 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 ------------------