Binary Heap

#include <bits/stdc++.h>
using namespace std;

struct Heap {
    vector<int> a;
    int sz = 0;

    Heap() { a.push_back(0); }

    bool cmp(int i, int j) { return a[i] < a[j]; }

    void up(int i) {
        while (i > 1 && cmp(i, i / 2)) {
            swap(a[i], a[i / 2]);
            i /= 2;
        }
    }

    void down(int i) {
        while (2 * i <= sz) {
            int j = 2 * i;
            if (j + 1 <= sz && cmp(j + 1, j)) j++;
            if (cmp(i, j)) break;
            swap(a[i], a[j]);
            i = j;
        }
    }

    void push(int x) { a.push_back(x); sz++; up(sz); }

    void pop() { swap(a[1], a[sz]); a.pop_back(); sz--; down(1); }

    int top() { return a[1]; }

    bool empty() { return sz == 0; }

    int size() { return sz; }
};