思路

• ph[k]第k个下标此时对应数组堆的位置为u
• hp[u]第u个数组堆中的元素插入的顺序为k
• h[i]当前数组堆中的i位置的数值

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5+10;
int n, m, a;

// heap中存储
class heap{
private:
    int hp[N];      // 第u个数组中的元素对应的插入顺序为k
    int ph[N];      // 第k个插入数此时对应在数组堆中的位置为u

    int cur_size;
public:
    int h[N];       // 当前堆的数值存储
    heap()
    {
        cur_size = 0;    
    }
    // 输入的u和v为此时的数值对应下标
    void heap_swap(int u, int v)
    {
        swap(h[u], h[v]);                // 数值上进行交换
        swap(hp[u], hp[v]);              // 当前插入次序下标交换,           hp[u] = k
        swap(ph[hp[u]], ph[hp[v]]);      // 当前插入第k个点此时的下标位置， ph[k] = u
    }
    void down(int u)
    {
        int t = u;
        if(2 * u <= cur_size && h[t] > h[2*u]) t = 2 * u;
        if(2 * u + 1 <= cur_size && h[t] > h[2*u+1]) t = 2 * u+1;
        if(u != t)
        {
            heap_swap(u, t);
            down(t);
        }
    }
    void up(int u)
    {
        if(u/2 > 0&& h[u] < h[u/2])
        {
            heap_swap(u, u/2);
            up(u >> 1);
        }
    }
    // k为第k个插入的数组
    void insert(int x, int k)
    {
        h[++cur_size] = x;
        ph[k] = cur_size;
        hp[cur_size] = k;
        up(cur_size);
    }
    // 删除的最小值
    void dm()
    {
        heap_swap(1,cur_size);
        cur_size--;
        down(1);
    }
    // 删除第k个插入的值
    void d(int k)
    {
        int u=ph[k];                    //这里一定要用u=ph[k]保存第k个插入点的下标
        heap_swap(u,cur_size);          //因为在此处heap_swap操作后ph[k]的值已经发生 
        cur_size--;                     //如果在up,down操作中仍然使用ph[k]作为参数就会发生错误
        up(u);
        down(u);
    }
    // 修改第k个插入的数
    void c(int k, int x)
    {
        h[ph[k]]=x;                     // 此处由于未涉及heap_swap操作且下面的up、down操作只会发生一个所以
        down(ph[k]);                    // 所以可直接传入ph[k]作为参数
        up(ph[k]);
    }
};

int main()
{
    cin>>n;
    int m=0;
    heap *hp = new heap();

    while(n--)
    {
        int k, x;
        string op;
        cin>>op;
        if(op=="I")
        {
            cin>>x;
            m++;
            hp->insert(x, m);
        }
        else if(op=="PM")    cout<<hp->h[1]<<endl;
        else if(op=="DM")
        {
            hp->dm();
        }
        else if(op=="D")
        {
            cin>>k;
            hp->d(k);
        }
        else if(op=="C")
        {
            cin>>k>>x;
            hp->c(k,x);
        }

    }
}