开始属实给👴绕晕了。
后来在纸上推了一遍。

首先清楚，模拟堆有5种操作，分别对应如下：

1. 插入一个数。`I x`，插入一个数 x。
2. 获取堆中最小值。`PM`，输出当前集合中的最小值；
3. 删除堆中的最小值。`DM`，删除当前集合中的最小值（数据保证此时的最小值唯一）；
4. 删除第k个插入的数。`D k`，删除第 k 个插入的数；
5. 修改第k个插入的数。`C k x`，修改第 k 个插入的数，将其变为 x；



此处因为涉及到了插入和修改第k个插入的节点，所以堆中的每个节点都需要维护三条信息：

```java
1.这个节点在堆中的位置信息，用下标idx表示
2.堆中下标为idx对应的这个节点是第k个插入的节点
3.这个第k个插入的节点所在堆中的位置下标idx    

所以在进行sink或者swim操作进行交换两个节点的时候，就需要一并交换这个节点所维护的这三条信息。

为了将这三条信息用代码记录，我们将这三条信息做如下定义：

1. 两个节点在堆中的位置下标: 
用一维数组heap[]表示堆, 两个节点下标分别记位i, j

2. 堆中idx对应的这个节点是第k个插入的节点：    
用一个一维数组来记录，设为hp[], 意思是heap to pointer,从堆到插入操作的映射    
比如hp[i] = k, 代表堆中第i个位置的节点是第k次插入的

3.这个第k个插入的节点所在堆中的位置下标idx：
还是用一个一维数组来记录，设为ph[], 意思是pointer to heap,从插入操作到堆的映射   
比如ph[k] = i, 代表第k次插入一个节点在堆中的位置下标为i    

那么接下来就是对两个节点进行交换操作，本质上也就是对上述节点中维护的三条信息的交换：

先构造一个swap函数：

public static void swap(int[] a, int i, int j){
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}

然后再对上述节点中维护的三条信息进行交换：

//第一条信息交换
//相当于先交换这两个节点的壳
swap(heap, i, j);    

//第二条信息交换
//然后交换这两个节点从堆位置下标到插入操作的映射
swap(hp, i, j);

//第三条信息交换
swap(ph, hp[i], hp[j]);
//此处有点绕，一层层分析：
//第三条信息交换的是插入操作到堆中位置下标的映射，按理说应该是ph[k] 和 ph[k + 1]交换,在函数中表示为swap(ph, k, k + 1);
//但是经过上述分析，hp[i] = k, hp[j] = k + 1,所以可以用它们代替

所以整合以下代码：

public static void heapSwap(int i, int j){
    swap(heap, i, j); 
    swap(hp, i, j);
    swap(hp, ph[i], ph[j]);
}
//顺序可以任意交换

懂了上述交换节点操作后，堆的这几个操作就不难了。

1.插入一个数。

思路：先是size增加，操作次数m增加，并记录第2，3条信息，然后将插入的数放在堆的末尾，并将插入的这个数做swim操作，以此调整为小根堆。

                size++;
                m++;
                ph[m] = size;
                hp[size] = m;

                heap[size] = x;
                swim(size);

2.获取最小值。

思路：最小值在小根堆根节点。

System.out.println(heap[1]);

3.删除最小值。

思路：直接将堆的最后一位元素覆盖根节点，对应swap操作，size减小，然后对根节点做sink操作，调整堆。

                heapSwap(1, size);
                size--;
                sink(1);

4.删除第k个数。

思路：先取出第k个数对应在堆中的下标idx。然后将堆的最后一位元素覆盖idx节点，对应swap操作，然后size–,对idx节点做sink/swim操作，调整堆。

                int idx = ph[k];
                heapSwap(idx, size);
                size--;
                sink(idx);
                swim(idx);

5.修改第k个节点。

思路：先取出第k个数对应在堆中的下标idx,然后将堆中此位置元素值改变为x，再对idx节点做sink/swim操作，调整堆。

                int idx = ph[k];
                heap[idx] = x;
                sink(idx);
                swim(idx);

完整代码：

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int N = 100010;
    static int size = 0;
    static int[] heap = new int[N];
    static int[] hp = new int[N];
    static int[] ph = new int[N];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line1 = br.readLine();

        int n = Integer.parseInt(line1);

        int m = 0;
        while (n-- > 0){
            String[] line2 = br.readLine().split(" ");

            String op = line2[0];
            int x, k;

            //插入操作
            if(op.equals("I")){
                x = Integer.parseInt(line2[1]);

                size++;
                m++;
                ph[m] = size;
                hp[size] = m;

                heap[size] = x;
                swim(size);
            }else if(op.equals("PM")){  //获取最小值
                System.out.println(heap[1]);
            }else if(op.equals("DM")){  //删除最小值
                heapSwap(1, size);
                size--;
                sink(1);
            }else if(op.equals("D")){  //删除第k个数
                k = Integer.parseInt(line2[1]);

                int idx = ph[k];
                heapSwap(idx, size);
                size--;
                sink(idx);
                swim(idx);
            }else {      //修改第k个数
                k = Integer.parseInt(line2[1]);
                x = Integer.parseInt(line2[2]);

                int idx = ph[k];
                heap[idx] = x;
                sink(idx);
                swim(idx);
            }
        }
        br.close();
    }

    public static void sink(int x){
        int t = x;

        if(2 * x <= size && heap[t] > heap[2 * x]){
            t = 2 * x;
        }

        if(2 * x + 1 <= size && heap[t] > heap[2 * x + 1]){
            t = 2 * x + 1;
        }
        if(t != x){
            heapSwap(t, x);
            sink(t);
        }
    }

    public static void swim(int x){
        while (x / 2 > 0 && heap[x / 2] > heap[x]){
            heapSwap(x / 2, x);
            x = x / 2;
        }
    }

    public static void swap(int[] a, int i, int j){
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    public static void heapSwap(int i, int j){
        swap(heap, i, j);
        swap(hp, i, j);     
        swap(ph, hp[i], hp[j]);       
    } 
}

看懂掌声。啪啪啪