minheap implementation in CPP

minheap.cpp

#include <bits/stdc++.h> 

using namespace std;

/* 
Time complexity:
   getMin() : O(1)
   extractMin(): O(LogN)
   decreaseKey : O(LogN)
   insert : O(LogN)
   deleteKey: O(LogN)
Uses : 
  Kth largest/smallest (use vice-versa data structure) 
  Dijkstra,Prim's MST 
  Priority Queue 
  
Working : 
  getMin(): return the root(topmost element) 
  insertKey(): we add a new key at the end and bubble it up as it as a chance to become the new root 
  decreaseKey(): we decrease the value of a key, and bubble it up as it as a chance to become the new root 
  deleteKey() : we put the minimum value in the node which we want to delete, so that it will be promoted to the new root,
  		then we extract the root, again we call the method heapify to balance the heap 
 extractMin(): replace the root value with last element, then we bubble down(Heapify) on that new root, to place it correctly. 
 
 
 
 To-do : corner cases 
 






*/ 
class MinHeap{
    private:
        vector<int> arr; 
        int heap_size; 
        int left(int i){ return (i*2) + 1; }
        int right (int i){return (i*2) +2; } 
        int parent(int i) { return (i-1)/2; } 
        
    public:
    MinHeap(){ heap_size = 0; }
    
    
    void Heapify(int i){   // top to down, bubble down(uses both left and right )
        int l= left(i);  
        int r= right(i); 
        int smallest = i; 
        if(l < arr.size() and arr[l] <  arr[smallest]) smallest = l ; 
        if(r<arr.size() and arr[r] <  arr[smallest]) smallest = r; 
        if(smallest != i){            // to make sure the heaps follow the heap property 
            swap(arr[smallest],arr[i]); 
            Heapify(i);       // recursively find the correct path 
        }
            
        
    }
    
    void insertKey(int val){
        arr.push_back(val); 
        int curr_elem_pos = arr.size()-1; 
        while(curr_elem_pos !=0 and arr[parent(curr_elem_pos)] > arr[curr_elem_pos]){ // bubble up, new key maybe the new root ? 
            swap(arr[parent(curr_elem_pos)],arr[curr_elem_pos]); 
            cout<<"swapping:" <<"\n"; 
            
            cout<<arr[parent(curr_elem_pos)] <<" "<<arr[curr_elem_pos]<<"\n"; 
            
            curr_elem_pos = parent(curr_elem_pos); 
            
        }
        
    }
    
    
    
    int getMin(){
        return arr.at(0); 
    }
    
    int extractMin(){
        int min_val = arr[0]; 
        
        swap(arr[0],arr[arr.size()-1]); 
        arr.pop_back();      // delete the last value, which is now the root. 
        Heapify(0);     // find new root 
        return min_val; 
        
    }
    
    void decreaseKey(int index, int value){ // a chance to become root, so bubble up 
        arr[index] = value; 
        while(index !=0 and arr[parent(index)] > arr[index]){
            swap(arr[parent(index)], arr[index]); 
            index = parent(index); 
        }
        
    }
    
    
    void deleteKey(int index){
        decreaseKey(index,INT_MIN); // promote to root 
        extractMin();      // delete the root 
        
    }
        
};
int main() {
	// your code goes here
    MinHeap h; 
    h.insertKey(3);
    h.insertKey(2);
    
    h.deleteKey(1);
    h.insertKey(15);
    h.insertKey(5);
    h.insertKey(4);
    h.insertKey(45);
    cout << h.extractMin() << " ";
    cout << h.getMin() << " ";
    h.decreaseKey(2, 1);
    cout << h.getMin();
	return 0;
}