6-堆

#include <iostream>
#include <string>
#include <utility>
 
using namespace std;
 
const int N = 100010;
 
// h[i]：堆中第 i 个位置存储的值
int h[N];
 
// hp[k]：第 k 个插入的数目前位于堆中的哪个位置
int hp[N];
 
// ph[i]：堆中第 i 个位置存储的是第几个插入的数
int ph[N];
 
// heap_size：当前堆中元素数量
// insert_count：总共执行过多少次插入操作
int heap_size, insert_count;
 
// 交换堆中的两个位置
void heap_swap(int a, int b) {
    swap(h[a], h[b]);
 
    // 更新“插入编号 -> 堆位置”的映射
    swap(hp[ph[a]], hp[ph[b]]);
 
    // 更新“堆位置 -> 插入编号”的映射
    swap(ph[a], ph[b]);
}
 
// 向下调整
void down(int u) {
    int t = u;
 
    if (u * 2 <= heap_size && h[u * 2] < h[t]) {
        t = u * 2;
    }
 
    if (u * 2 + 1 <= heap_size && h[u * 2 + 1] < h[t]) {
        t = u * 2 + 1;
    }
 
    if (t != u) {
        heap_swap(t, u);
        down(t);
    }
}
 
// 向上调整
void up(int u) {
    while (u / 2 > 0 && h[u] < h[u / 2]) {
        heap_swap(u, u / 2);
        u /= 2;
    }
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n;
    cin >> n;
 
    while (n--) {
        string op;
        cin >> op;
 
        if (op == "I") {
            int x;
            cin >> x;
 
            heap_size++;
            insert_count++;
 
            h[heap_size] = x;
 
            // 第 insert_count 个插入的数位于 heap_size
            hp[insert_count] = heap_size;
 
            // 堆中 heap_size 位置存的是第 insert_count 个插入的数
            ph[heap_size] = insert_count;
 
            up(heap_size);
        } else if (op == "PM") {
            cout << h[1] << '\n';
        } else if (op == "DM") {
            // 把堆顶和最后一个元素交换，再删除最后一个元素
            heap_swap(1, heap_size);
            heap_size--;
 
            down(1);
        } else if (op == "D") {
            int k;
            cin >> k;
 
            // 找到第 k 个插入的数目前在堆中的位置
            int position = hp[k];
 
            // 将它和最后一个元素交换，再删除
            heap_swap(position, heap_size);
            heap_size--;
 
            // 交换过来的元素可能需要向上或向下调整
            up(position);
            down(position);
        } else if (op == "C") {
            int k, x;
            cin >> k >> x;
 
            // 找到第 k 个插入的数目前在堆中的位置
            int position = hp[k];
 
            h[position] = x;
 
            // 修改后可能变小，也可能变大
            up(position);
            down(position);
        }
    }
 
    return 0;
}