Min Heap

heap.cpp

////////////////////////////////////////////
// @title Implement of Min-Heap
// @author Joonas <joonas.yoon@gmail.com>
// @blog https://joonas.tistory.com
////////////////////////////////////////////

#define MAX_SIZE 100001

template <typename T>
class MinHeap {
private:
    int sz;
    T a[MAX_SIZE];
public:
    MinHeap() {
        sz = 0;
    }
    bool empty() {
        return sz == 0;
    }
    void clear() {
        sz = 0;
    }
    T top() { // or peek()
        return a[0];
    }
    void pop() {
        a[0] = a[--sz];
        heapify(0);
    }
    void push(T data) {
        a[sz] = data;
        for (int i = sz++; i;) {
            int p = (i - 1) >> 1;
            if (a[p] < a[i]) break;
            swap(a[p], a[i]);
            i = p;
        }
    }
private:
    void heapify(int p) {
        int l = 2 * p + 1;
        int r = l + 1;
        int k = p;
        if (l < sz && a[l] < a[k]) k = l;
        if (r < sz && a[r] < a[k]) k = r;
        if (k != p) {
            swap(a[k], a[p]);
            heapify(k);
        }
    }
};