题解：
维护一个集合，初始时集合为空，支持如下几种操作：
①I x，插入一个数 \(x\)；
②PM，输出当前集合中的最小值；
③DM，删除当前集合中的最小值（数据保证此时的最小值唯一）；
④D k，删除第 \(k\) 个插入的数；
⑤C k x，修改第 \(k\) 个插入的数，将其变为 \(x\)；
现在要进行 \(N\) 次操作，对于所有第 \(2\) 个操作，输出当前集合的最小值。
原题链接：839. 模拟堆 - AcWing
堆是一种特殊的完全二叉树
优先级队列（小根堆的模拟实现）未央.303的博客-CSDN
小根堆的性质：每个结点的值都小于其左孩子和右孩子结点的值。（大根堆反之）
结点h[x]的左孩子为h[x * 2]，右孩子为h[x * 2 + 1]。
小根堆的两种基本操作（递归）：
- 上升
up()：只要当前结点小于其父节点，则将其与父节点交换； - 下降
down()：只要当前结点大于其孩子结点，则将其与孩子节点中的较小值交换；
堆的五种基本操作：
- 插入一个数：
heap[++size]=x;up(size);
在末尾插入，随后让其上升到合适的位置。 - 求集合中的最小值：
heap[1];
根节点一定为最小值。 - 删除最小值：
heap[1]=heap[size];size--;down(1);
数组的性质：删除第一个结点难，而删除最后一个结点易。
令最后一个结点直接覆盖最小的根节点，比起直接删除第一个结点更方便。 - 删除任意一个元素：
heap[k]=heap[size];size--;down(k);up(k);
当删除堆中间的元素时，不能确定该节点和其父节点、左右孩子结点的关系；
故同时执行down(k);up(k);操作，实际上只有其中一者会被执行。 - 修改任意一个元素：
heap[k]=x;down(k);up(k);
关键点：h hp ph 之间的映射关系
ph[k]=u：第 \(k\) 个点的下标为 \(u\)hp[u]=k：节点 \(u\) 是第 \(k\) 个插入的- 若
hp[u]=k，则ph[k]=u
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, cnt, siz;
int h[N]; //堆
int ph[N]; //ph[k]=u: 第k个点的下标为u
int hp[N]; //hp[u]=k: 节点u是第k个插入的
//映射关系：若hp[u]=k，则ph[k]=u
void heap_swap(int u, int v) {
swap(h[u], h[v]);
swap(hp[u], hp[v]);
swap(ph[hp[u]], ph[hp[v]]);
}
void down(int u) {
int tmp = u;
//左孩子存在，且左孩子小于当前节点
if (u * 2 <= len && h[u * 2] < h[tmp])
tmp = u * 2;
//右孩子存在，且右孩子小于当前节点和左孩子
if (u * 2 + 1 <= len && h[u * 2 + 1] < h[tmp])
tmp = u * 2 + 1;
if (u != tmp) { //根节点不是当前最小值
swap(h[u], h[tmp]);
down(tmp); //递归
}
}
void up(int u) {
if (u / 2 > 0 && h[u / 2] > h[u]) {
heap_swap(u, u / 2);
up(u / 2);
}
}
int main()
{
cin >> n;
while (n--)
{
string op;
int k, x;
cin >> op;
if (op == "I") {
cin >> x;
h[++siz] = x; //插入队尾
cnt++; //更新是第k个插入的数
ph[cnt] = siz; //记录第k个插入的数的下标
hp[siz] = cnt; //记录该点是第k个插入的
up(siz);
}
else if (op == "PM") {
cout << h[1] << endl;
}
else if (op == "DM") {
heap_swap(1, siz--);
down(1);
}
else if (op == "D") {
cin >> k;
int tmp = ph[k];
heap_swap(tmp, siz--);
up(tmp);
down(tmp);
}
else if (op == "C"){
cin >> k >> x;
h[ph[k]] = x;
down(ph[k]);
up(ph[k]);
}
}
return 0;
}