AcWing 839. 模拟堆

2020-12-25 05:28

阅读:680

标签: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


评论


亲,登录后才可以留言!