Question

Write the code for binary min heap in c++ .

Answer 1

#include<iostream>
#include<climits>
using namespace std;

//class for heap
class Heap{
   //pointer to store heap value
   int *heap;
   //variable to store number of values in heap
   int current_size;
   //variable to store maximum capacity of heap
   int max_capacity;
  
   public:
       //constructor
       Heap(int n){
           max_capacity=n;
           current_size=0;
           heap=new int[max_capacity];
       }
       //methods to get parent, lef and right child index
       int parent(int i) {
           return (i-1)/2;
       }
        int leftChild(int i) {
          return (2*i + 1);
       }
        int rightChild(int i) {
           return (2*i + 2);
       }
       //method to insert value to heap
       void insert(int value){
           if (current_size != max_capacity) {
               current_size++;
               int i = current_size - 1;
               heap[i] = value;

               // Fix the min heap property if it is violated
               while (i != 0 && heap[parent(i)] > heap[i]) {
                   int temp=heap[i];
                   heap[i]=heap[parent(i)];
                   heap[parent(i)]=temp;
                      i = parent(i);
               }
               cout<<"Inserted "<<value<<"\n";
           }else{
               cout << "\nHeap Full!!!! Could not insert the value\n";
           }

       }
       //method to get minimum value in heap
       int getMin(){
               return heap[0];
       }
       //method to minhepify the heap
       void MinHeapify(int i){
           int l = leftChild(i);
           int r = rightChild(i);
          
           int smallest = i;
          
           if (l < current_size && heap[l] < heap[i])
               smallest = l;
           if (r < current_size && heap[r] < heap[smallest])
               smallest = r;
  
           if (smallest != i) {
               int temp=heap[i];
               heap[i]=heap[smallest];
               heap[smallest]=temp;

               MinHeapify(smallest);
           }
       }
       //method to delete and return minimu value in heap
       int extractMin(){
           if (current_size == 1) {
                current_size--;
               return heap[0];
           }
           if (current_size <= 0)
               return INT_MAX;
      

           int min = heap[0];
            heap[0] = heap[current_size-1];
           current_size--;
           MinHeapify(0);

           return min;
       }
  
};
//main method
int main(){
   //creating heap of max capacity 10
   Heap h1(10);
   h1.insert(5);
   h1.insert(2);
   h1.insert(3);
   h1.insert(1);
   h1.insert(10);
   cout<<"Minum element in heap: "<<h1.getMin()<<"\n";
   int d=h1.extractMin();
   if(d!=INT_MAX)
       cout<<"Minimum element deleted: "<<d<<"\n";
   else
       cout<<"Heap is empty\n";
      
   cout<<"Minum element in heap: "<<h1.getMin()<<"\n";
   return 0;
}

//####################### PGM END ##################################

OUTPUT
###########