Min_Heap.cpp

#include <iostream>
using namespace std;

class MinHeap {
private:
    int* heap;
    int size;
    int capacity;

    int parent(int i) { return i / 2;}

    int left(int i) { return 2 * i;}

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

    void upHeapify(int i) {
        while (i > 1 && heap[parent(i)] > heap[i]) {
            swap(heap[i], heap[parent(i)]);
            i = parent(i);
        }
    }

    void downHeapify(int i) {
        int smallest = i;
        int l = left(i);
        int r = right(i);

        if (l <= size && heap[l] < heap[smallest])
            smallest = l;

        if (r <= size && heap[r] < heap[smallest])
            smallest = r;

        if (smallest != i) {
            swap(heap[i], heap[smallest]);
            downHeapify(smallest);
        }
    }

public:
    MinHeap(int cap) {
        capacity = cap;
        size = 0;
        heap = new int[capacity + 1];
    }

    ~MinHeap() {
        delete[] heap;
    }

    bool isEmpty() {
        return size == 0;
    }

    bool isFull() {
        return size == capacity;
    }

    void insert(int x) {
        if (isFull()) {
            cout << "Heap Overflow\n";
            return;
        }
        heap[++size] = x;
        upHeapify(size);
    }

    int extractMin() {
        if (isEmpty()) {
            cout << "Heap Empty\n";
            return -1;
        }
        int root = heap[1];
        heap[1] = heap[size--];
        downHeapify(1);
        return root;
    }

    int getMin() {
        if (isEmpty()) return -1;
        return heap[1];
    }

    int getSize() {
        return size;
    }
};