题解 | #【模板】堆#

#include<algorithm>
#include<iostream>

using namespace std;
const int N = 100010;
int siz, h[N];
void up(int u){
    while(u > 1 && h[u / 2] < h[u]){
        swap(h[u], h[u / 2]);
        u /= 2;
    }
}
void down(int u){
    int t = u;
    if(u * 2 <= siz && h[u * 2] > h[t]) t = u * 2;
    if(u * 2 + 1 <= siz && h[u * 2 + 1] > h[t]) t = u * 2 + 1;
    if(u != t){
        swap(h[u], h[t]);
        down(t);
    }
}

int main() {
    int n;
    cin >> n;
    while(n --){
        string op;
        cin >> op;
        if(op == "push"){
            int x;
            cin >> x;
            h[++ siz] = x;
            up(siz); 
        }
        else if(op == "top")
            if(siz) cout << h[1] << endl;
            else cout << "empty" << endl;
        else{
            if(siz){
                cout << h[1] << endl;
                h[1] = h[siz --];
                down(1);
            }
            else cout << "empty" << endl;
        }
    }
    return 0;
}