AcWing 839. 模拟堆

#include <iostream>
#include <stdio.h>
using namespace std;
const int N =100010;
int a[N], b[N],hi[N],num,idx;
//b[idx]记录第idx个元素的序号
//hi[]存储idx,当前元素是第几个元素，hi[序号]=idx（第几个元素）
void hswap(int t, int u){
    swap(b[hi[t]], b[hi[u]]);//交换当前序号
    swap(hi[t], hi[u]);//交换k的值
    swap(a[t],a[u]);
}
void up(int u){
    while(u / 2 && a[u] < a[u / 2]){
        hswap(u, u/2);
        u = u / 2;
    }
}
void down(int u){
    int t = u;
    if(u * 2 <= num && a[t] > a[u * 2]) t = u * 2;
    if(u * 2 + 1 <= num && a[t] > a[u * 2 + 1]) t = u * 2 + 1;
    if(u != t){
        hswap(t , u);
        down(t);
    }
}
int main(){
    int n,x,k;
    // idx=0;
    cin >> n;
    while(n--){
        char op[5];
        cin >> op;
        if(op[0] == 'I'){
            cin >> x;
            idx++;
            num++;
            b[idx] = num;
            hi[num] = idx;
            a[num] = x;
            up(num);
        }else if(op[0] == 'P'){
            cout << a[1] << endl;
        }else if(op[1] == 'M'){
            hswap(1, num);//不只是交换数值,还交换了下标和序号等信息
            num--;
            down(1);
        }else if(op[0] == 'D'){
            cin >> k;
            k = b[k];//k是临时变量,不会因为b[]的变化而变化
            hswap(k, num);
            num--;
            up(k);
            down(k);
        }else if(op[0] == 'C'){
            cin >> k >> x;
            k = b[k];//k是临时变量,不会因为b[]的变化而变化
            a[k] = x;
            up(k);
            down(k);
        }
    }
    return 0;
}