模拟堆（Java版）
题目描述：
维护一个集合，初始时集合为空，支持如下几种操作：
- 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);
}
}
}难点：弄清三个数组分别是干什么的，并搞清之间的映射关系
腾讯云开发者
