模拟堆（Java版）

import java.io.*;
public class Main {
    static int N=100010;
    static int []h=new int[N];
    static int []ph=new int[N],hp=new int[N];
    static int size=0;  //堆中元素的数量
    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int n=Integer.parseInt(br.readLine());
        int m=0;
        while (n-->0){
            String []s=br.readLine().split(" ");
            if("I".equals(s[0])){
                int x=Integer.parseInt(s[1]);
                h[++size]=x;
                m++;  //第几次插入
                ph[m]=size;
                hp[size]=m;
                up(size);
            }else if("PM".equals(s[0])){
                System.out.println(h[1]);
            }else if("DM".equals(s[0])){
                // 为啥用最后一个元素覆盖第一个元素？因为删除第一个点不方便
                heapSwap(1,size);
                // h[1] = h[size --]; 不能写成这种，因为要维持映射
                size--;
                down(1);
            }else if("D".equals(s[0])){
                int k=Integer.parseInt(s[1]);
                // 将第k次插入的元素，转换为堆中的下标
                int u=ph[k];
                heapSwap(u,size);
                size--;
                // 下面两个操作只会执行其中一个
                down(u); up(u);
            }else {
                int k=Integer.parseInt(s[1]);
                int x=Integer.parseInt(s[2]);
                h[ph[k]]=x;
                down(ph[k]); up(ph[k]);
            }
        }
        br.close();
    }
    // 应用于堆的交换
    private static void heapSwap(int i, int j) {
        swap(h,i,j); // 交换堆中两个元素的值
        swap(hp,i,j); // 维护堆到位置的映射
        swap(ph,hp[i],hp[j]);// 维护位置到堆的映射
    }
    //交换数组的两个元素
    private static void swap(int[] a, int i, int j) {
        int tmp=a[i];
        a[i]=a[j];
        a[j]=tmp;
    }
    // down操作是看一个元素是否需要往下移动
    private static void down(int i) {
      int t=i;
      // 如果左儿子存在 并且 左儿子比根节点小，就使 t 保存 左儿子下标
      if(i*2<=size &&h[i*2]<h[t]) t=2*i;
      if(i*2+1<=size &&h[i*2+1]<h[t]) t=2*i+1;
      if(t!=i){
          heapSwap(i,t);
          down(t);
      }
    }
    private static void up(int i) {
        // 只要根节点存在，并且u这个节点的值 比 根节点小，就需要交换
      if(i/2>0 && h[i/2]>h[i]){
         heapSwap(i,i/2);
         up(i/2);
      }
    }
}