2.数据结构：7.模拟堆

ph 数组的下标表示的是第 k 个插入的数，对应的值表示的是对应到 heap 里面的下标。比如说，刚开始的时候是 m ，对应的是 mysize 。那么就有 ph[m]=mysize, hp[mysize]=m

#include<algorithm>
#include<cstring>
#include<iostream>

using namespace std;

const int N=100010;
int n;
int mysize;
int m;
int h[N];
int ph[N];
int hp[N];

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(2*u<=mysize&&h[2*u]<h[t]){
        t=2*u;
    }
    if(2*u+1<=mysize&&h[2*u+1]<h[t]){
        t=2*u+1;
    }
    if(t!=u){
        heap_swap(t,u);
        down(t);
    }
}

void up(int u){
    while(u/2&&h[u]<h[u/2]){
        heap_swap(u,u/2);
        u/=2;
    }
}

int main(){
    cin>>n;
    while(n--){
        char op[10];
        cin>>op;
        if(!strcmp(op,"I")){
            int x;
            cin>>x;
            m++;
            mysize++;
            h[mysize]=x;
            ph[m]=mysize;
            hp[mysize]=m;
            up(mysize);
        }else if(!strcmp(op,"PM")){
            printf("%d\n",h[1]);
        }else if(!strcmp(op,"DM")){
            heap_swap(1,mysize);
            mysize--;
            down(1);
        }else if(!strcmp(op,"D")){
            int k;
            cin>>k;
            k=ph[k];
            heap_swap(k,mysize);
            mysize--;
            down(k);
            up(k);
        }else{
            int k,x;
            cin>>k>>x;
            k=ph[k];
            h[k]=x;
            up(k);
            down(k);
        }
    }
    
    return 0;
}