题面

题解（手写小根堆）

down 操作 ：向下更新，将父节点和两个子节点比较，值小的作为父节点，然后递归更新

up 操作 ：向上更新 ，将此节点与其父节点比较，如果此节点的值小于父节点，就交换位置，然后继续向上更新

1. “I x”，插入一个数x； 只需要在堆的最后插入一个数，然后up
2. “PM”，输出当前集合中的最小值； 只需要返回序列中的第一个元素
3. “DM”，删除当前集合中的最小值（数据保证此时的最小值唯一）； 就是删除堆顶元素，我们可以让堆里的最后一个元素，将堆顶元素覆盖，再将新的堆顶元素down一遍
4. “D k”，删除第k个插入的数； 将最后一个元素覆盖第k个插入的元素，然后down一遍
5. “C k x”，修改第k个插入的数，将其变为x；先将第k个元素修改，修改完后值要么变大要么变小，我们可以down，up一遍（这两个只会执行一种）
6. 补充： O(n) 的建堆方式 ：for ( int i = n / 2 ; i >= 1 ; i-- ) down ( i ) ; 因为最后一层不需要down（有n/2个元素），直接从到数第二层开始 down

代码

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>

using namespace std;
const int N = 1e5 + 10;

int n, m;
int h[N], cnt;
int ph[N];  //ph[i]=j 表示第i个插入的点的在堆中下标是j
int hp[N]; //hp[i]=j 表示在堆中下标为i的点是第j个插入的点


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 << 1) <= cnt && h[t] > h[u << 1]) t = u << 1;
    if ((u << 1 | 1) <= cnt && h[t] > h[u << 1 | 1]) t = u << 1 | 1;
    if (u != t) {
        heap_swap(t, u);
        down(t);
    }
}


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

int main() {

    m = 0;
    cin >> n;
    string op;
    int k, x;
    while (n--) {
        cin >> op;
        if (op == "I") {
            cin >> x;
            cnt++;
            m++;
            ph[m] = cnt;  //第m个插入的数在堆中的下标为size
            hp[cnt] = m;  //下标为size的数是第m个插入的数
            h[cnt] = x;
            up(cnt);
        } else if (op == "PM") {
            cout << h[1] << endl;
        } else if (op == "DM") {
            heap_swap(1, cnt);
            cnt--;
            down(1);
        } else if (op == "D") {
            cin >> k;
            k = ph[k];//第k个插入的数在堆中的下标
            heap_swap(k, cnt);
            cnt--;
            down(k), up(k);
        } else {
            cin >> k >> x;
            k = ph[k];
            h[k] = x;
            down(k), up(k);
        }
    }
    return 0;
}