Index-Heap { Push, Pop, Modify }

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

template<class T = int>
struct MinHeap {
    const T _INFINTY = -1;
    vector<T> val;
    unordered_map<T, size_t> pos;
    MinHeap() {
        val = { _INFINTY };
        pos.clear();
    }
    int size() { return int(val.size()) - 1; }
    void swap_all(size_t i, size_t j) {
        swap(val[i], val[j]);
        swap(pos[val[i]], pos[val[j]]);
    }
    void push_up(size_t i) {
        for(; val[i] < val[i >> 1]; i >>= 1)
            swap_all(i, i >> 1);
    }
    void push_down(size_t i) {
        for (size_t heap_size = size();
            (i << 1) < heap_size && val[i] > val[i << 1];
            i <<= 1)
            swap_all(i, i << 1);
    }
    void modify(const T& old_val, const T& new_val) {
        size_t i = pos[old_val];
        val[i] = new_val;
        push_up(i);
        push_down(i);
    }
    void push(const T& value) {
        val.push_back(value);
        pos[value] = size();
        push_up(size());
    }
    T min() {
        assert(size() > 0);
        return val[1];
    }
    T pop() {
        assert(size() > 0);
        T return_val = min();
        swap_all(1, size());
        val.pop_back();
        push_down(1);
        return return_val;
    }
};

bool test_heap() {
    MinHeap<int> q;
    q.push(3);
    q.push(2);
    if (q.min() != 2) return false;
    q.modify(3, 1);
    if (q.pop() != 1) return false;
    if (q.pop() != 2) return false;
    return true;
}

int main() {
    cout << (test_heap()? "May be a good heap." : "Bad heap.") << endl;
    return 0;
}