题解 | #【模板】堆#

#include <iostream>
#include <cmath>
using namespace std;
typedef long long ll;
const int MAXN = 100010;
ll ans[MAXN];
int cnt = 1;

void down(ll* arr, ll mid) {
    ll left = mid * 2 ;
    ll right = mid * 2 + 1 ;
    ll largest = mid;
    if (left < cnt && arr[left] > arr[largest])
        largest = left;
    if (right < cnt && arr[right] > arr[largest])
        largest = right;
    if (largest != mid) {
        swap(arr[largest], arr[mid]);
        down(arr, largest);
    }
}

void Push(ll* arr, ll n) {
    ans[cnt] = n;
    cnt++;
    for(int i = (cnt-1)/2; i>0;i--) down(arr,i);
}

void Top(ll* arr) {
    if (cnt != 1) {
        cout << arr[1] << endl;
        return;
    }
    cout << "empty" << endl;
}

void Pop(ll* arr) {
    if (cnt != 1) {
        cout << arr[1] << endl;
        cnt--;
        arr[1] = arr[cnt];
        down(arr,1);
    } else {
        cout << "empty" << endl;
        return;
    }
}


int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n;
    cin >> n;
    string ss;
    ll a;
    while (n--) {
        cin >> ss;
        if (ss == "push") {
            cin >> a;
            Push(ans, a);
        }
        if (ss == "pop") {
            Pop(ans);
        }
        if (ss == "top") {
            Top(ans);
        }
    }
    return 0;
}