0839

839. 模拟堆

题目

维护一个集合，初始时集合为空，支持如下几种操作：

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

现在要进行 $N$ 次操作，对于所有第 $2$ 个操作，输出当前集合的最小值。

输入格式

第一行包含整数 $N$。

接下来 $N$ 行，每行包含一个操作指令，操作指令为 I x， PM， DM， D k 或 C k x 中的一种。

输出格式

对于每个输出指令 PM，输出一个结果，表示当前集合中的最小值。

每个结果占一行。

数据范围

$1 \le N \le 10^5$

$-10^9 \le x \le 10^9$

数据保证合法。

输入样例：

8
I -10
PM
I -10
D 1
C 2 8
I 6
PM
DM

输出样例：

-10
6

题解

前置题目：0838

前置知识：堆排序

本题知识：数据结构-堆

题目分析

用数组实现堆，同时支持一些操作

其中和堆排序不同的是需要支持删除第 $k$ 个插入的数和修改第 $k$ 个插入的数

这样就需要记录第 $k$ 个插入的数在堆中是什么位置，但是在堆的上移和下沉操作时插入的值在堆中的位置会改变，这样原来记录的第 $k$ 个插入的数在堆中是什么位置就不准确了。

因此还需要通过在堆中的位置定位到是第几个插入的，同时更新这个值。这样就保证了指针指向的正确性。

// 第 cnt 个插入的数是堆中下标为 size 的值
ph[cnt] = size
// 堆中下标为 size 的值是第 cnt 个被插入的
hp[size] = cnt

核心swap操作

func heapSwap(u, v int) {
	swap(&hp[u], &hp[v])
	swap(&ph[hp[u]], &ph[hp[v]])
	swap(&h[u], &h[v])
}