#define HMAX 10005
struct HpNode {
    int dis, u;
} hp[HMAX];
int hsz;

// 小根堆
bool cmp(const struct HpNode* a, const struct HpNode* b) {
    return a->dis > b->dis;
}

void h_down_node(int pos) {
    struct HpNode t = hp[pos];
    for (int i=pos*2+1; i<hsz; i=i*2+1) {
        if (i+1<hsz && cmp(&hp[i], &hp[i+1])) i = i+1; 
        if (cmp(&t, &hp[i])) {
            hp[pos] = hp[i]; pos = i;
        } else break;
    }
    hp[pos] = t;
}

void h_up_node(int pos) {
    struct HpNode o = hp[pos];
    // 上浮
    while (pos && cmp(&hp[pos-1>>1], &o)) {
        hp[pos] = hp[pos-1>>1];
        pos = pos-1>>1;
    }
    hp[pos] = o;
}

void heap_init() {
    hsz = 0;
}

void heap_add(const struct HpNode o) {
    assert(hsz+1<HMAX);
    hp[hsz] = o;
    // 上浮
    h_up_node(hsz);
    hsz++;
}

struct HpNode heap_top() {
    return hp[0];
}

void heap_pop() {
    assert(hsz>0);
    hsz--;
    hp[0] = hp[hsz];
    h_down_node(0);
}