复习模拟堆

维护一个集合，初始时集合为空，支持如下几种操作：

1. “I x”，插入一个数x；
2. “PM”，输出当前集合中的最小值；
3. “DM”，删除当前集合中的最小值（当最小值不唯一时，删除最早插入的最小值）；
4. “D k”，删除第k个插入的数；
5. “C k x”，修改第k个插入的数，将其变为x；

现在要进行N次操作，对于所有第2个操作，输出当前集合的最小值。

输入格式

第一行包含整数N。

接下来N行，每行包含一个操作指令，操作指令为”I x”，”PM”，”DM”，”D k”或”C k x”中的一种。

输出格式

对于每个输出指令“PM”，输出一个结果，表示当前集合中的最小值。

每个结果占一行。

数据范围

$1≤N≤10^5$

$-10^9 \leq n \leq 10^9$

数据保证合法。

输入样例：

8
I -10
PM
I -10
D 1
C 2 8
I 6
PM
DM

输出样例：

-10
6

#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
const int N = 1e5 + 10;

int h[N], hp[N], ph[N], sz;
//h[N]:下标为i的对应堆中的值
//hp[N]: heap-pointer 堆中第i个位置对应的第k次插入
//ph[N]: pointer-heap 下标为k的对应在堆中的第i的位置
//sz: 堆中目前元素数目


void head_swap(int x, int y) {
    swap(h[x], h[y]);
    swap(ph[hp[x]], ph[hp[y]]);
    swap(hp[x], hp[y]);
}

void down(int x) {
    int t = x;
    if(x*2 <= sz && h[x*2] < h[t]) t = x*2;
    if(x*2+1 <= sz && h[x*2+1] < h[t]) t = x*2+1;
    if(t != x) {
        head_swap(t, x);
        down(t);
    }
}

void up(int x) {
    //当父节点不为空且大于子节点时交换
    while(x/2 && h[x/2] > h[x]) {
        head_swap(x/2, x);
        x /= 2;
    }
}

int main() {
    int n, idx = 0;
    scanf("%d", &n);
    while(n--) {
        char op[10];
        int k, x;
        scanf("%s", &op);
        if(!strcmp(op, "I")) {
            cin >> x;
            sz++;
            idx++;
            ph[idx] = sz, hp[sz] = idx;
            h[sz] = x;
            up(sz);
        } else if(!strcmp(op, "PM")) {
            printf("%d\n", h[1]);
        } else if(!strcmp(op, "D")) {
            cin >> k;
            k = ph[k];
            head_swap(k, sz);
            sz--;
            down(k), up(k);
        } else if(!strcmp(op, "C")) {
            cin >> k >> x;
            k = ph[k];
            h[k] = x;
            down(k), up(k);
        } else {
            head_swap(1, sz);
            sz--;
            down(1);
        }
    }
    return 0;
}