$\huge \color{orange}{成仙之路->}$ $\huge \color{purple}{算法基础课题解}$

注意：

1. ph[m] = cnt表示第 m 个插入的数的下标是 cnt，hp[cnt] = m表示下标是 cnt 的数是第 m 个插入的数
2. heap_swap(a,b)表示交换 h[a] 和 h[b],并维护 ph 和 hp 两个数组
3. 删除第 k 个数时，需要提前把第 k 个数的下标存储起来

完整代码

#include<bits/stdc++.h>

using namespace std;

const int N = 100010;

int n;
string op;
int k,x;
int h[N],ph[N],hp[N],cnt,m;

//交换h[a]和h[b],并维护ph和hp两个数组
void heap_swap(int a,int b)
{
    swap(h[a],h[b]);
    swap(ph[hp[a]],ph[hp[b]]);
    swap(hp[a],hp[b]);
}

//往下移
void down(int u)
{
    int t=u;
    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;
    if(u!=t)
    {
        heap_swap(u,t);
        down(t);
    }
}

//往上移
void up(int u)
{
    while(u/2&&h[u/2]>h[u])
    {
        heap_swap(u,u/2);
        u>>=1;
    }
}

int main()
{
    cin>>n;

    while(n--)
    {
        cin>>op;

        //插入一个数 x
        if(op=="I")
        {
            cin>>x;
            ph[++m]=++cnt;
            hp[cnt]=m;
            h[cnt]=x;
            up(cnt);
        }

        //输出当前集合中的最小值
        if(op=="PM") cout<<h[1]<<endl;

        //删除当前集合中的最小值
        if(op=="DM") 
        {
            heap_swap(1,cnt--);
            down(1);
        }

        //删除第 k 个插入的数
        if(op=="D")
        {
            cin>>k;
            k=ph[k];
            heap_swap(k,cnt--);
            down(k);
            up(k);
        }

        //修改第 k 个插入的数，将其变为 x
        if(op=="C")
        {
            cin>>k>>x;
            h[ph[k]]=x;
            down(ph[k]);
            up(ph[k]);
        }
    }

    return 0;
}