)
先看手写堆的相关问题：堆排序（手写堆）
五大操作：
例题：
输入样例：
8 I -10 PM I -10 D 1 C 2 8 I 6 PM DM
期望输出:
-10 6
代码实现：
#include<bits/stdc++.h>
using namespace std;const int N =1e5+10;
int h[N];
int n,size;
int ph[N],hp[N];void hswap(int a,int b)
{swap(h[a],h[b]);swap(ph[a],ph[b]);swap(hp[a],hp[b]);
}void down(int u)
{int t=u;if(u*2<=size && h[u*2]<h[t]) t=u*2;if(u*2+1<size &&h[u*2+1]<h[t]) t=u*2+1;if(u!=t){hswap(u,t);down(t);}
}void up(int u)
{while(u/2 &&h[u/2]>h[u]){hswap(u/2,u);u=u/2;}
}int main()
{cin>>n;int k=0;//用来存储插入顺序for(int i=1;i<=n;i++){char op[3];int a,b;scanf("%s",op);if(!strcmp(op,"I")){cin>>a;size++;k++;ph[k]=size;hp[size]=k;h[size] = a;up(size);}else if (!strcmp(op,"PM")) cout<<h[1]<<endl;else if (!strcmp(op,"DM")){hswap(1,size);size --;down(1);}else if (!strcmp(op,"D")){cin>>a;a=ph[a];hswap(a,size);size--;down(a);up(a);//这里down和up只会执行一个}else{cin>>a>>b;a=ph[a];h[a]=b;down(a);up(a);}}return 0;
}
