例题及代码模板

模拟堆

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

I x，插入一个数 x ；
PM，输出当前集合中的最小值；
DM，删除当前集合中的最小值（数据保证此时的最小值唯一）；
D k，删除第 k 个插入的数；
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 ≤ x ≤ 10^9  
数据保证合法。

输入样例：

8
I -10
PM
I -10
D 1
C 2 8
I 6
PM
DM
输出样例：

-10
6
 

#include 
#include 
#include 
using namespace std;
const int N = 100010;
int n,m,hp[N],ph[N];
//ph[k]存的是第k个插入的数在堆中的下标是什么
//hp[k]堆里面的某一个点是第几个插入的点
int h[N],size;
void heap_swap(int a, int b) {//a和b是下标swap(ph[hp[a]],ph[hp[b]]);//交换ph数组中记录的下标；通过hp获得是第几次插入的，通过第k次插入的获得某一元素在堆中的下标//因为ph是通过第k次为下标存储的，所以我们想修改ph数组的值，必须找到第k次//而hp是通过下标存储k的值的，所以先通过已知的下标找到k的值，再交换ph里面的值swap(hp[a],hp[b]);//交换插入的顺序，即存储的k的值swap(h[a],h[b]);//交换两个元素的值
}
void down(int u) {int t = u;//使用t记录根节点的值//让根节点分别和左右子节点进行对比if(u*2<=size&&h[u*2]h[u]) {heap_swap(u/2,u);u/=2;}
}
int main() {int n,m=0;scanf("%d",&n);while(n--) {char op[10];int k,x;scanf("%s",&op);if(!strcmp(op,"I")) {scanf("%d",&x);size++;m++;ph[m]=size;//记录第m次插入的元素在堆里面的下标hp[size]=m;//记录当前下标的元素在ph里面的位置，即当前元素是第m个插入的h[size]=x;//插入元素up(size);//调整堆} else if(!strcmp(op,"PM"))//输出最小值printf("%d\n",h[1]);else if(!strcmp(op,"DM")) {//删除最小值heap_swap(1,size);size--;down(1);} else if(!strcmp(op,"D")) {//删除第k个插入的元素scanf("%d",&k);k=ph[k];//第k个元素所存储的下标heap_swap(k,size);//通过第k个元素的下标将第k个元素与最后一个元素进行交换size--;//删除第k个插入的元素down(k),up(k);//两个操作最多只会执行一个操作} else {scanf("%d%d",&k,&x);k=ph[k];//找到第k次插入的元素的存储下标h[k]=x;//通过下标修改第k次插入元素的值down(k),up(k);//维护堆}}return 0;
}