题解 | #【模板】堆#

#include<bits/stdc++.h>
#include <vector>
using namespace std;
void down(int u, vector<int>& a, int mysize) {
    int t = u;
    if (u * 2 <= mysize && a[u * 2] > a[t]) t = u * 2;
    if (u * 2 + 1 <= mysize && a[u * 2 + 1] > a[t]) t = u * 2 + 1;
    if (u != t) {
        swap(a[u], a[t]);
        down(t, a, mysize);
    }
    return;
}
void up(int u, vector<int>& a) {
    int t = u;
    if (u % 2 == 0 && u / 2 >= 1 && a[u / 2] < a[t]) t = u / 2;
    else if (u % 2 == 1 && (u - 1) / 2 >= 1 && a[(u - 1) / 2] < a[t]) t = (u - 1) / 2;
    if (u != t) {
        swap(a[u], a[t]);
        up(t, a);
    }
    return;
}
int main() {
    int n = 0, mysize = 0, x = 0;
    cin >> n;
    vector<int> a(n + 1, 0);
    while (n--) {
        string s;
        cin >> s;
        if (s == "push") {
            cin >> x;
            mysize++;
            a[mysize] = x;
            up(mysize, a);
        } else if (s == "top") {
            if (a[1]) {
                cout << a[1] << endl;
            } else {
                cout << "empty" << endl;
            }
        } else {
            if (a[1]) {
                cout << a[1] << endl;
                swap(a[1], a[mysize]);
                a[mysize] = 0;
                mysize--;
                down(1, a, mysize);
            } else {
                cout << "empty" << endl;
            }
        }
    }
}