题目描述：
维护一个集合，初始时集合为空，支持如下几种操作：
I x，插入一个数 x；
PM，输出当前集合中的最小值；
DM，删除当前集合中的最小值（数据保证此时的最小值唯一）；
D k，删除第 k 个插入的数；
C k x，修改第 k 个插入的数，将其变为 x；
现在要进行 N 次操作，对于所有第 2 个操作，输出当前集合的最小值。
样例：
输入：
8
I -10
PM
I -10
D 1
C 2 8
I 6
PM
DM
输出：
-10
6
如何手写一个堆？
堆的定义：根节点的值 小于等于 左右子节点的值（小根堆）。
存储采用一维数组（模拟最小堆，下标从1开始）：x点的左儿子是：2x，x的右儿子是：2x+1
维护两个操作down 和 up
插入一个数
heap[ ++ size] = x; up(size)
求集合当中的最小值
heap[1]
删除最小值
heap[1] = heap[size]; size --; down(1);
为啥用最后一个元素覆盖第一个元素，因为删除第一个点不方便
删除任意一元素
heap[k] = heap[size]; size--; down(k); up(k)
后面两个操作只会执行一个或者不执行，因为变小才会向上走，变小向上走，或者不变
修改任意一个元素
heap[k] = x; down(x); up(x)
思路分析：
h[]: 存储堆里的元素
ph[]: 代表位置到堆的映射
hp[]: 代表堆到位置的映射
需要一个堆的数组是毋庸置疑的，创建下面两个数组的目的是什么呢？
ph[]数组
当执行删除第k个元素时，堆内元素会根据小根堆的性质不断移动，所以需要一个数组辅助去记住第几个插入的下标。 ph[k] = i:表示第k个插入的数在堆里面的下标为i。
hp[]数组
当我们交换了在堆里面下标为a、b这两个元素后，此时ph数组记录的插入顺序就错了，因为堆里面元素互换了。要想让ph数组正确，就需要互换ph[a],ph[b]。而要互换ph数组，就必须知道ph数组中的哪两个记录a、b的插入顺序。这时候你们可能会说，ph数组不是已经记录了吗？没错，ph数组是记录了，但是它是单向的，是ph数组指向堆元素下标的，而我们只知道堆元素的下标，我们怎么可能知道ph数组中的哪两个指向的a、b呢？所以必须开一个数组来存储堆里面下标为的元素是第几个插入的。使它们是双向的，这样才能互换ph数组。hp数组就是为了互换ph数组而服务的。
hp[j]：代表在堆的下标为j的元素 是第哪一次插入的
映射关系: 若hp[j] = k，则ph[k] = j。
详细代码（带注释）
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); } } }
难点：弄清三个数组分别是干什么的，并搞清之间的映射关系
