AcWing 839. 模拟堆
标签:amp turn can while std ons return ++ 赋值
AcWing 839. 模拟堆
#include
using namespace std;
const int N=1e6+10;
// h[N]存储堆中的值, h[1]是堆顶,x的左儿子是2x, 右儿子是2x + 1
// ph[k]存储第k个插入的点在堆中的位置
// hp[k]存储堆中下标是k的点是第几个插入的
int h[N],ph[N],hp[N],num;
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*2h[u])
heap_swap(u/2,u),u/=2;
}
int main(){
int n,m=0;
scanf("%d",&n);
while(n--){
char op[3];
int k,x;
scanf("%s",op);
if(!strcmp(op,"I")){
scanf("%d",&x);
num++;
m++;
//堆中的位置
ph[m]=num;
//位置上的点是第几个插入的
hp[num]=m;
//赋值
h[num]=x;
//up操作
up(num);
}
else if(!strcmp(op,"PM")) printf("%d\n",h[1]);
else if(!strcmp(op,"DM")){
heap_swap(1,num);
num--;
down(1);
}
else if(!strcmp(op,"D")){
scanf("%d",&k);
k=ph[k];
heap_swap(k,num);
num--;
down(k),up(k);
}
else{
scanf("%d%d",&k,&x);
k=ph[k];
h[k]=x;
down(k),up(k);
}
}
return 0;
}
AcWing 839. 模拟堆
标签:amp turn can while std ons return ++ 赋值
原文地址:https://www.cnblogs.com/wiseXu/p/13401374.html
评论