堆模拟

#include<iostream>
#include<string.h>
using namespace std;
const int N=100010;
int h[N],hp[N],ph[N];//hp,ph,映射第k个插入的数字的位置，和位置为m的数是第几个插入的，两个数组互相映射
void heap_swap(int a,int b){
  //交换时映射也需要改变，a，b表示下标，
    swap(hp[ph[a]],hp[ph[b]]);
    swap(ph[a],ph[b]);
    swap(h[a],h[b]);
}
int siz;//堆中总数
void down(int u){
    int t=u;
    if(2*u<=siz&&h[t]>h[2*u]) t=2*u;//判断两个子节点中数与本节点的大小关系
    if(2*u+1<=siz&&h[t]>h[2*u+1]) t=2*u+1;//
    if(t!=u){
        heap_swap(u,t);
        down(t);//递归
    }
}
void up(int u){
    while(u/2&&h[u/2]>h[u]){//判断是否还有父节点
        heap_swap(u,u/2);
        u/=2;
    }
}
int main(){
    int k,x;
    int n=0,m=0;
    scanf("%d",&n);
    while(n--){
        char op[10];
        scanf("%s",op);
        if(!strcmp(op,"I")){
            scanf("%d",&x);
            m++,siz++;
            ph[siz]=m,hp[m]=siz;
            h[siz]=x;
            up(siz);
        }else if(!strcmp(op,"DM")){
            heap_swap(1,siz);
            siz--;
            down(1);
        }else if(!strcmp(op,"D")){

            scanf("%d",&k);
            k=hp[k];
            heap_swap(k,siz);
            siz--;
            down(k),up(k);
        }else if(!strcmp(op,"PM")){
            cout<<h[1]<<endl;
        }else{

            scanf("%d%d",&k,&x);
            h[hp[k]]=x;
            down(hp[k]);
            up(hp[k]);
        }
    }
    return 0;
}