手写堆

主要是记录写法。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 10;
int heap[MAXN], size = 0;

void push(int x) {
    heap[++size] = x;
    int tmp = size;
    while (tmp > 1) {
        int next = tmp >> 1;
        if (heap[tmp] >= heap[next])
            return ;
        swap(heap[next], heap[tmp]);
        tmp = next;
    }
    return ;
}

void pop() {
    heap[1] = heap[size--];
    int tmp = 1;
    while (tmp << 1 <= size) {
        int next = tmp << 1;
        if (next < size && heap[next] > heap[next + 1])
            next++;
        if (heap[tmp] <= heap[next])
            return ;
        swap(heap[tmp], heap[next]);
        tmp = next;
    }
    // pop() 操作比较陌生，可以着重记一下
}

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

int main() {
    int n;
    scanf("%d", &n);
    for (int opt, x; n; n--) {
        scanf("%d", &opt);
        switch (opt) {
            case 1 : {
                scanf("%d", &x);
                push(x);
                break;
            }
            case 2 : {
                printf("%d\n", top());
                break;
            }
            case 3 : {
                pop();
                break;
            }
        }
    }
    return 0;
}