题目描述

原题

维护一个集合，初始时集合为空，支持如下几种操作：

I x，插入一个数 x；
PM，输出当前集合中的最小值；
DM，删除当前集合中的最小值（数据保证此时的最小值唯一）；
D k，删除第 k 个插入的数；
C k x，修改第 k 个插入的数，将其变为 x；
现在要进行 N 次操作，对于所有第 2 个操作，输出当前集合的最小值。

输入格式
第一行包含整数 N。

接下来 N 行，每行包含一个操作指令，操作指令为 I x，PM，DM，D k 或 C k x 中的一种。

输出格式
对于每个输出指令 PM，输出一个结果，表示当前集合中的最小值。

每个结果占一行。

数据范围
1≤N≤105
−109≤x≤109
数据保证合法。

输入样例：
8
I -10
PM
I -10
D 1
C 2 8
I 6
PM
DM
输出样例：
-10
6

算法：数组模拟堆

2022-4-5:更新图中结点的标识。操作的解释
1. I x，插入一个数 x；(直接插入到最后，然后不断up使之有序)
2. PM，输出当前集合中的最小值；（输出堆顶）
3. DM，删除当前集合中的最小值（数据保证此时的最小值唯一）；（和最后一个元素交换删除最后一个元素）
4. D k，删除第 k 个插入的数；（第k个数和最后一个数交换，删除最后一个；交换的那个数down或者up一遍，使之有序）
5. C k x，修改第 k 个插入的数，将其变为 x；（修改值之后，down或者up一遍）
PS：为了简化代码，对于每个点的更改情况，我们不写判断，直接down或者up一遍，使之有序，因为他们要么大往下走，要么小往上走，只会执行其中的一个。

参考文献

y总

C++ 代码

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

using namespace std;

const int N = 100010;
//h数组模拟的堆   ph数组：第几个插入的点，从左边指向右边的点  
//hp数组：从右边指向左边的点，ph的映射     cnt堆的大小
int h [N] , ph[N] , hp[N] , cnt;

/*
交换两个点，映射也要改变
*/
void heap_swap(int a  , int b ){
    //图中的蓝色虚线
    swap(ph[hp[a]] , ph[hp[b]]);
    //图中绿色的线
    swap(hp[a] , hp[b]);
    //第三步，交换a ， b两个点
    swap(h[a] , h[b]);
}

/*
down操作就是判断当前这个点和它的左右子结点的关系，如果说父结点更大，那么就
会和较小的点交换，把小的点换下去，然后可能换下去之后这个点还是下面子堆之中
的较大点，所以递归去做。
*/
void down(int u){
    //用t来表示三个结点之间的最小值：即当前结点和它的左右孩子结点
    int t = u ;
     //先看一下左孩子是否在堆中 ， 并进行判断是不是比此时的t小，是就更新t
    if(u * 2 <= cnt && h[u * 2] < h[t]) t = u * 2;
     //下面的右孩子结点同理
    if(u * 2 + 1 <= cnt && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    //最后t存储的就是三个结点之间的最小值
    //如果u！=t ， 说明u就不是最小值
    if(u != t){
         //交换
        heap_swap(u , t);
        //递归处理
        down(t);
    }

}

/*
up操作和down相反，当堆中某个点变小的时候，就需要up把这个小的点给移上去，同样
移上去之后也可能和父结点、另外一个子结点相比，他还是最小的，所以也需要递归来
做。
*/
void up(int u){
    //当根结点大于孩子结点的时候，就需要把孩子结点给移上去，也就是交换
    while(u / 2 && h[u / 2] > h[u]){
        heap_swap(u / 2 , u);
        u /= 2;
    }

}

int main(){
    //m:当前是插入的第几个数。因为删除的时候要删除第k个插入的数，所以要用个变量存下来
    int n , m = 0;
    scanf("%d" , &n);
    //n条命令
    while(n --){
        //op字符数组，记录每次的操作
        char op[5];
        //k:在第k个数进行的操作  x：插入的元素值
        int k  , x ;
        //读取操作
        scanf("%s" , &op);
        /*
        strcmp函数是string compare(字符串比较)的缩写，用于比较两个字符串
        并根据比较结果返回整数。基本形式为strcmp(str1,str2)，若str1=str2，
        则返回零；若str1<str2，则返回负数；若str1>str2，则返回正数
        */
        if(!strcmp(op , "I")){//插入
            scanf("%d" , &x);
            //长度对应相加
            cnt++;
            m++;
            //刚开始元素插入的时候在堆中最后面的位置即cnt。同样hp里面的映射也记录下
            ph[m] = cnt, hp[cnt] = m;
            //堆中放入要插入的数
            h[cnt] = x;
            //做完之后，up一遍
            up(cnt);
        }else if(!strcmp(op , "PM")){//输出当前集合中的最小值
            printf("%d\n" , h[1]);//也就是数组里面的第一个
        }else if(!strcmp(op , "DM")){//删除最小值
            //把最小值交换到末尾，长度减1 ，就完成删除
            heap_swap(1, cnt);
            //然后长度对应减少
            cnt--;
            //然后对交换到根结点的值进行down操作，恢复小根堆
            down(1);
        }else if(!strcmp(op ,"D")){//删除第k个插入的数
            scanf("%d" , &k);
            //让k找到在堆里面的位置，用到那个映射的数组
            k = ph[k];
//下面的操作就和删除元素一样了，由于不确定这个数的大小，所以down和up都要进行一遍
            heap_swap(k , cnt);
            cnt--;
            down(k) ,  up(k);

        }else{//修改第k个插入的数
            scanf("%d%d" , &k , &x);
            //同样，先把第k个数在堆中的位置给找出来
            k = ph[k];
            //找到堆中位置的数后，替换x
            h[k] = x;
            //下面还是进行down和up操作。做多只会执行其中的一个
            down(k);
            up(k);
        }
    }
    return 0;
}