A1476 大根堆

// A1476 大根堆 —— 用优先队列（堆）维护
//
// 操作 1：把 x 压入堆；操作 2：输出堆顶（也就是最大值）；操作 3：弹出堆顶。
// 堆为空时，操作 2、3 自动跳过。
//
// 堆用完全二叉树 + 下标表示：位置 i 的父亲是 i/2，左孩子 2i，右孩子 2i+1。
// 插入时新元素先放到队尾，再与父亲比较、比父亲大就上浮；
// 删除堆顶时把队尾元素换到堆顶，再与孩子比较、比孩子小就下沉。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    priority_queue<int> heap; // 大根堆：堆顶永远是当前最大值
    while (n--) {
        int op;
        cin >> op;
        if (op == 1) {
            int x;
            cin >> x;
            heap.push(x); // 插入：放到队尾，与父亲比较后上浮
        } else if (op == 2) {
            if (!heap.empty()) {
                cout << heap.top() << '\n'; // 查询最大值 = 堆顶
            }
        } else if (op == 3) {
            if (!heap.empty()) {
                heap.pop(); // 删除最大值：删掉堆顶，把队尾换上来再下沉
            }
        }
    }
    return 0;
}