题解 | #【模板】堆#

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