Min Heap Implementation

Min heap is an almost complete binary tree in which root element's value is lesser than all children and the same rule applies for all other nodes as well.

// A C++ program to showcase the common min heap operations

#include <iostream>
using namespace std;

void swapValues(int *a, int *b){
    int t = *a;
    *a = *b;
    *b = t;
}

// A class for minHeap
class MinHeap{
    int *harr; // pointer to array of elements in min heap
    int capacity; //maximum capacity of heap
    int current_size; // count of elements currently present  in heap
    public:
        MinHeap(int capacity); // constructor
        int getMin(); // minimum element of the heap
        int extractMin(); // extract minimum element from the heap
        int left(int i); // index of left child of the element present at index i
        int right(int i); // index of right child of the element present at index i
        int parent(int i); // index of the parent of the element present at index i
        void minHeapify(int i); // helper function to maintain the minHeap property of min heap
        void insertKey(int k); // insert a value k in heap
        void deleteKey(int i); // delete key present at index i
        void decreaseKey(int i, int new_val); //decrease value at index i with new_val
};

MinHeap::MinHeap(int cap){
    current_size = 0;
    capacity = cap;
    harr = new int[capacity];
}

int MinHeap::left(int i){
    return (2*i +1);
}

int MinHeap::right(int i){
    return (2*i+2);
}

int MinHeap::parent(int i){
    if(i<=0) return -1;
    return (i-1)/2;
}

int MinHeap::getMin(){
    return harr[0];
}

void MinHeap::minHeapify(int i){
    int l = left(i);
    int r = right(i);
    int smallest = i;
    if(l < current_size && harr[l] < harr[smallest])
        smallest = l;
    if(r < current_size && harr[r] < harr[smallest])
        smallest = r;
    if(smallest != i){
        swapValues(&harr[i], &harr[smallest]);
        minHeapify(smallest);
    }
}

void MinHeap:: decreaseKey(int i, int new_val){
    if(new_val > harr[i])
        return;
    harr[i] = new_val;
    while(i!=0 && harr[parent(i)] > harr[i]){
       swapValues(&harr[parent(i)], &harr[i]);
       i = parent(i);
    }
}

int MinHeap:: extractMin(){
    if(current_size <= 0)
        return INT_MAX;
    if(current_size == 1){
        current_size--;
        return harr[0];
    }
    int min_val = harr[0];
    harr[0] = harr[current_size-1];
    current_size--;
    minHeapify(0);
    return min_val;
}

void MinHeap:: deleteKey(int i){
    decreaseKey(i, INT_MIN);
    extractMin();
}

void MinHeap:: insertKey(int k){
    if(current_size == capacity){
        cout<<"Heap Overflow"<<endl;
        return;
    }
    // insert your val at the last
    harr[current_size] = k;
    int i = current_size;
    current_size++;
   // to maintain the min heap property
    while(i!=0 && harr[parent(i)] > harr[i]){
        swapValues(&harr[parent(i)], &harr[i]);
        i = parent(i);
    }
}

int main()
{
    MinHeap h(20);
    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;
}