下面是我二刷的时候自己想到的算法,因为中间有一个地方手滑写错了debug了很久,所以有部分代码使用来debug没删
我这里把每次输入都当做是一个节点,索引对应着次序,节点的值就是数的值
然后,让小根堆存储的是插入的次序(而不是值),之所以这样设计是因为通过插入次序是可以确定值的.
然后在比较的时候用值比较就好.
最后由于要确定第k个插入的数是哪个结点,因此要新建一个findn数组记录,并在每次交换结点的时候更新.

import java.util.*;
class Main{
    static int[] heap=new int[100010];
    static int[] cv=new int[100010];
    static int[] findn=new int[100010];//通过次序找到堆中的结点
    static int node=0;//表示在堆中的结点
    static int index=0;//表示插入的顺序
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        while(n-->0){
            String s=sc.next();
            if("I".equals(s)){
                int x=sc.nextInt();
                insert(x);
            }
            else if("PM".equals(s)){
                //  System.out.println(pop());

            }
            else if("DM".equals(s)){
                delete();

            }
            else if("D".equals(s)){
                int k=sc.nextInt();
                delete(k);
            }
            else if("C".equals(s)){
                int k=sc.nextInt();
                int x=sc.nextInt();
                change(k,x);
            }
        }
    }
    static void up(int x){
        int top=x/2;
        if(top!=0&&cv[heap[top]]>cv[heap[x]]){
            int temp=heap[top];
            heap[top]=heap[x];
            heap[x]=temp;
            findn[heap[top]]=top;
            findn[heap[x]]=x;
            up(top);
        }
    }
    static void insert(int x){
        cv[++index]=x;//表示第index插入的值是x
        heap[++node]=index;//通过堆中的结点能找到是第几个插入的数
        findn[index]=node;//通过第几次插入的数也能找到堆中的结点是几
        up(node);
        System.out.println("--------插入"+x+"此时的堆排序------");
        show();
    }

    static int pop(){
        return cv[heap[1]];
    }
    static void down(int x){
        int t=x;
        if(2*x<=node&&cv[heap[t]]>cv[heap[2*x]]) t=2*x;
        if(2*x+1<=node&&cv[heap[t]]>cv[heap[2*x+1]]) t=2*x+1;
        if(x!=t){
            int temp=heap[t];
            heap[t]=heap[x];
            heap[x]=temp;
            findn[heap[x]]=x;
            findn[heap[t]]=t;
            down(t);
        }
    }
    static void delete(){
        heap[1]=heap[node];
        findn[heap[1]]=1;
        node--;
        down(1);
        System.out.println("--------删掉头此时的堆排序------");
        show();
    }
    static void delete(int x){
        System.out.println("--------删掉第"+x+"个插入的此时的堆排序------");
        int fn=findn[x];
        heap[fn]=heap[node];
        findn[heap[fn]]=fn;
        node--;
        up(fn);
        down(fn);
        show();
    }
    static void change(int k,int x){
        System.out.println("--------修改第"+k+"个插入的为"+x+"此时的堆排序------");
        cv[k]=x;
        int fn=findn[k];
        up(fn);
        down(fn);
        show();
    }
    static void show(){
        int count=1;
        for(int i=1;i<=node;i++){
            int size= (int) Math.pow(2,count);
            System.out.print(cv[heap[i]]+"("+heap[i]+")  ");
            if(i==size-1){
                System.out.println();
                count++;
            }
        }
        System.out.println();
    }
}