Binary_Heap_Implementation

// Implementation of Binary Heap in C++
// Detailed explanation video: https://youtu.be/A9iBOFDfD8Q
// ------------------------------------------------------------

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

class MinHeap{
    vector<int> heap;
    
    int parent(int i) { return (i-1)/2; }
    int left(int i) {return (2*i + 1);}
    int right(int i) {return (2*i + 2);}
    
    void heapify(int i){
        int l = left(i);
        int r = right(i);
        int smallest = i;
        if(l < heap.size() && heap[l] < heap[i])
            smallest = l;
        if(r < heap.size() && heap[r] < heap[smallest])
            smallest = r;
        if(smallest != i){
            std::swap(heap[i], heap[smallest]);
            heapify(smallest);
        }
    }
public:
    int getMin(){ 
        if(heap.size() == 0)
            return -1;
        return heap.front();
    }
    
    void insert(int k){
        heap.push_back(k);
        int i = heap.size() - 1;
        while(i != 0 && heap[parent(i)] > heap[i]){
            std::swap(heap[i], heap[parent(i)]);
            i = parent(i);
        }
    }
    
    void deleteMin(){
        if(heap.size() == 0){
            cout << "Heap is empty" << endl;
            return;
        }
        heap[0] = heap.back();
        heap.pop_back();
        heapify(0);
    }
    
    int size() {return heap.size();}
    
    void printHeap() {
        for(int i = 0; i < heap.size(); ++i)
            cout << heap[i] << "\t";
        cout << endl;
    }
    
};

int main() {
    MinHeap H;
    H.insert(20);
    H.insert(8);
    H.insert(5);
    H.insert(10);
    H.insert(15);
    H.insert(12);
    H.printHeap();
    cout << "Min = " << H.getMin() << endl;
    H.deleteMin();
    H.printHeap();
    
    return 0;
}