什么是堆？

• 一颗完全二叉树，根是整棵树的最小值
• 每一层的子节点都大于对应根节点

堆的模板(不考虑数是第几个插入的)

int h[N];    //value
int idx;    //树的大小
//将当前的数向下排序
void down(int num){
    int t = num;
    
    if(num * 2 <= idx && h[num * 2 ] < h[t]) t = num * 2;
    if(num * 2 + 1 <= idx && h[num * 2 + 1] < h[t]) t = num * 2 + 1;
    
    if(t != num){
        swap(h[t],h[num]);
        down(t);
    }
}
//将当前的数向上排序
void up(int num){
    if(num >> 1 && h[num] < h[num >> 1]){
        swap(h[num],h[num >> 1]);
        up(num >> 1);
    }
}
//将n个数据初始化成一个堆。
    for(int i = 1;i <= n;i ++) cin >> h[i];
    idx = n;
    //从倒数第二层开始做down
    for(int i = n >> 1;i;i --) down(i);

//插入操作
void ins(int num){
    idx ++;
    
    h[idx] = num;
    
    down(idx),up(idx);    //up和down最多只会执行一个，所以不考虑下标变换
}

//删除最小值
void del(){
    swap(h[1],h[idx]);
    
    idx --;
    
    down(1);
}

也是模板(考虑是第几个插入的)

//h存的是value，hp存的是idx映射的cnt，ph存的是cnt映射的idx，idx为树里的下标，cnt为插入的序号
int h[N],hp[N],ph[N];
int cnt;
int idx;
//头部交换
void head_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 num){
    int t = num;
    
    if(num * 2 <= idx && h[num * 2] < h[t]) t = num * 2;
    if(num * 2 + 1 <= idx && h[num * 2 + 1] < h[t]) t = num * 2 + 1;
    
    if(t != num){
        head_swap(t,num);
        down(t);
    }
}
//往上排序
void up(int num){
    if(num / 2 && h[num / 2] > h[num]){
        head_swap(num,num / 2);
        up(num / 2);
    }
}

//插入一个数
void ins(int a){
        idx ++;    //堆里面有几个数
        cnt ++;    //第k个插入的数
        //映射
        ph[cnt] = idx;
        hp[idx] = cnt;
        
        h[idx] = a;
        up(idx);
}

//删除第k个插入的数
void del_k(int a){
        //一定要注意保留原来指向的值，不然会在后面的swap里被改变
        a = ph[a];
        
        head_swap(a,idx);
        idx --;
        
        down(a),up(a);    //down和up可能都会执行
}

//将第k个插入的数的值改成b
void change_k(int a,int b){
        //一定要注意保留原来指向的值，不然会在后面的swap里被改变
        a = ph[a];
        h[a] = b;
        
        down(a),up(a);    //down和up可能都会执行
}

模拟堆

#include<iostream>
#include<cstring>

using namespace std;

const int N = 100010;
//h存的是value，hp存的是idx映射的cnt，ph存的是cnt映射的idx，idx为树里的下标，cnt为插入的序号
int h[N],hp[N],ph[N];
int cnt;
int idx;
//头部交换
void head_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 num){
    int t = num;
    
    if(num * 2 <= idx && h[num * 2] < h[t]) t = num * 2;
    if(num * 2 + 1 <= idx && h[num * 2 + 1] < h[t]) t = num * 2 + 1;
    
    if(t != num){
        head_swap(t,num);
        down(t);
    }
}

//往上排序
void up(int num){
    if(num / 2 && h[num / 2] > h[num]){
        head_swap(num,num / 2);
        up(num / 2);
    }
}

int main(){
    int n;
    cin >> n;
    
    while(n --){
        int a,b;
        char op[10];
        
        scanf("%s",op);
        
        if(!strcmp(op,"I")){
            cin >> a;
            
            idx ++;
            cnt ++;
            
            ph[cnt] = idx;
            hp[idx] = cnt;
            
            h[idx] = a;
            up(idx);
        }else if(!strcmp(op,"PM")) cout << h[1] << endl;
        else if(!strcmp(op,"DM")){
            head_swap(1,idx);
            
            idx --;
            
            down(1);
        }else if(!strcmp(op,"C")){
            cin >> a >> b;
            //一定要注意保留原来指向的值，不然会在后面的swap里被改变
            a = ph[a];
            h[a] = b;
            
            down(a);
            up(a);
        }else{
            cin >> a;
            //一定要注意保留原来指向的值，不然会在后面的swap里被改变
            a = ph[a];
            
            head_swap(a,idx);
            idx --;
            
            down(a);
            up(a);
        }
    }
    
    return 0;
}