【题目来源】
AcWing：839. 模拟堆 - AcWing题库
【题目描述】
维护一个集合，初始时集合为空，支持如下几种操作：
（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，输出一个结果，表示当前集合中的最小值。每个结果占一行。
【输入样例】
8
I -10
PM
I -10
D 1
C 2 8
I 6
PM
DM
【输出样例】
-10
6
【解题思路】
【算法标签】
《AcWing 839 模拟堆》 #堆#
【代码详解】
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int n; // n操作指令数量
int heap[N], hsize; // heap堆，从下标1开始放数据。hsize堆大小
// point-to-heap[i]: 第i个插入元素在堆中下标是pth[i]，堆中下标是i的元素
int pth[N], htp[N]; // 第i个元素 -> 堆下标; 堆下标 -> 第i个元素// 堆数组heap中下标是a,b
void heap_swap(int a, int b)
{swap(pth[htp[a]], pth[htp[b]]);swap(htp[a], htp[b]);swap(heap[a], heap[b]);
}
// 节点u与左右儿子比较
void down(int u) //调整第u个元素，与其左右子节点比较
{int t=u;if (u*2<=hsize && heap[u*2]<heap[t]) //根大要调整t = u*2;if (u*2+1<=hsize && heap[u*2+1]<heap[t]) //根大要调整t = u*2+1;if (t!=u) {heap_swap(u, t); //子节点t移到下标u变为根节点down(t); //父节点u移到下标t处，继续与新儿子}
}
// 节点u向上比较（与父节点比较）生成小根堆
void up(int u)
{while (u/2>=1 && heap[u/2]>heap[u]) {heap_swap(u/2, u);u = u/2;}
}
int main()
{int inum=0; //第inum次插入char op[5];cin >> n; // n操作指令数量while (n--) {int k, x;cin >> op;// strcmp比较两个字符串大小，相等返回0if (!strcmp(op, "I")) { // I x, 插入一个数xcin >> x;hsize++; inum++;pth[inum]=hsize; htp[hsize]=inum;heap[hsize]=x;up(hsize);} else if (!strcmp(op, "PM")) // PM输出当前集合中的最小值cout << heap[1] << endl;else if (!strcmp(op, "DM")) { // DM删除当前集合中的最小值heap_swap(1, hsize);hsize--;down(1); // 与子节点比生成小根堆}else if (!strcmp(op, "D")) { // D k 删除第k个插入的数cin >> k;k = pth[k]; // 第k个插入的数在堆中下标heap_swap(k, hsize);hsize--;down(k); //堆调整up(k);}else { // C k x, 修改第k个插入的数，将其变为xcin >> k >> x;k = pth[k]; // 第k个插入的数在堆中下标heap[k] = x;down(k); // 堆调整up(k);}}return 0;
}
【运行结果】
8
I -10
PM
-10
I -10
D 1
C 2 8
I 6
PM
6
DM