C++ 代码

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 100010;

// 题目要求删除第k个插入的数
// hp[N]表示的是第k个插入的数的下标：通俗的说hp数组下标表示的是第几个插入的，存的是第几个插入的下标
// ph[N]表示的是某个下标是第k个插入的点：同上，hp数组与ph数组是两个是互逆的数组

int h[N], hp[N], ph[N], cnt;


void heap_swap(int a, int b) {
    // 
    swap(ph[hp[a]], ph[hp[b]]);
    swap(hp[a], hp[b]);
    swap(h[a], h[b]);
}

void down(int u) {
    int t = u;
    if (u * 2 <= cnt && h[u * 2] < h[t]) t = u * 2;
    if (u * 2 + 1 <= cnt && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    if (u != t) {
        heap_swap(u, t);
        down(t);
    }
}

void up(int u) {
    while ( u >> 1 && h[u] < h[u >> 1]) {
        heap_swap(u, u >> 1);
        u >>= 1;
    }
}


int main() {
    int n = 0, m = 0;
    scanf("%d", &n);

    while ( n --) {
        char op[5];
        int k, x;
        scanf("%s", op);
        if (!strcmp(op, "I")) {
            scanf("%d", &x);
            cnt ++;
            m ++;
            ph[m] = cnt, hp[cnt] = m;
            h[cnt] = x;
            up(cnt);
        } 
        else if (!strcmp(op, "PM")) printf("%d\n", h[1]);
        else if (!strcmp(op, "DM")) {
            heap_swap(1, cnt);
            cnt --;
            down(1);
        }
        else if (!strcmp(op, "D")) {
            scanf("%d", &k);
            k = ph[k];
            heap_swap(k, cnt);
            cnt --;
            up(k);
            down(k);
        }
        else {
            scanf("%d%d", &k, &x);
            k = ph[k];
            h[k] = x;
            up(k);
            down(k);
        }
    }

    return 0;
}