本系列所有题目均为Acwing课的内容，发表博客既是为了学习总结，加深自己的印象，同时也是为了以后回过头来看时，不会感叹虚度光阴罢了，因此如果出现错误，欢迎大家能够指出错误，我会认真改正的。同时也希望文章能够让你有所收获，与君共勉！
昨天被并查集折磨了一天，今天终于可以放松点了。那么今天就主要来学习堆的操作。
这里的堆主要为大顶堆和小顶堆，他们都是以完全二叉树作为数据结构的（完全二叉树不清楚的可以自己去百度下），而完全二叉树一般用数组模拟。接下来谈谈堆能干什么，我们知道每个父节点比子节点的值要大的堆是大顶堆，那么最大值也就是堆顶喽，小顶堆同理，最小值也是堆顶，有了这样的数据结构我们就能以\(O(1)\)的时间复杂度获得最大值和最小值，而堆的主要操作分别是插入一个元素，删除一个元素，修改一个元素，获得集合中最小的元素。具体的就在下面讲吧。
模拟堆
维护一个集合，初始时集合为空，支持如下几种操作：
I x，插入一个数 x；
PM，输出当前集合中的最小值；
DM，删除当前集合中的最小值（数据保证此时的最小值唯一）；
D k，删除第 k 个插入的数；
C k x，修改第 k 个插入的数，将其变为 x；
现在要进行 N 次操作，对于所有第 2 个操作，输出当前集合的最小值。
输入格式
第一行包含整数 N。
接下来 N 行，每行包含一个操作指令，操作指令为 I x，PM，DM，D k 或 C k x 中的一种。
输出格式
对于每个输出指令 PM，输出一个结果，表示当前集合中的最小值。
每个结果占一行。
数据范围
1≤N≤105
−109≤x≤109
数据保证合法。
输入样例：
8
I -10
PM
I -10
D 1
C 2 8
I 6
PM
DM
输出样例：
-10
6
算法原理
初始化
刚刚我们知道堆是用数组实现的完全二叉树h[N]，除此之外要想实现堆操作，还需要定义cnt始终指向堆中最后一个结点（其实这时的cnt就是这个元素在堆中的下标）和进来的顺序m，以及表示存储x是第几个进来的数组hp[N]和存储第m个进来的数在堆h[N]中所对应的下标ph[N]。（这里m和cnt在数组都是从1开始，这样初始化m=cnt=0时就要先++m,++cnt）。
差点忘了，建立一个堆就是不断下沉元素的过程。
插入一个元素
在堆中我们插入一个元素是给h[cnt] = x，同时需要记录这个元素是第几个进来的hp[cnt] = m以及这时进来的元素在堆中存储的下标也要被存储起来ph[m] = cnt，并且将这个元素上浮down(k)（因为是存储在堆最后的位置的）来寻找这个元素应该在堆中存储的位置。
cin >> x;
++cnt,++m;
h[cnt] = x;
hp[cnt] = m,ph[m] = cnt;
up(cnt);
删除任意一个元素
众所周知，数组删除可以用覆盖来代替，那么如果我们需要删除第k个数，我们通常会用最后一个数覆盖他（方便），这里的覆盖就是堆交换heap_swap(k,cnt)，然后调整最后一个数到它应该到的位置，即上浮下沉一遍up(k).down(k)，从树的角度就是把最后一个数看看是往上走，还是往下走。
修改结点值
修改跟删除一样h[k] = x，删除完之后就调整修改后节点的位置，即上浮下沉一遍。
获得集合里的最值
这个更简单，下标为1的结点就是堆顶h[1]，就是最大值或最小值，直接输出就行。
这些操作中就有堆的核心操作，上浮和下沉，还有堆交换（比较难理解），接下来就来介绍这些核心操作，以小顶堆为例。
上浮（参数是元素在堆中的下标）
由小顶堆的性质我们可以知道，如果一个节点比他的父节点小，那么我们就需要把他上浮，那么怎么上浮呢，我们可以一直比较该节点与其父节点的大小，如果比它小，就进行堆交换，那么什么时候停止呢？当该节点比父节点要大时就满足小顶堆性质了，可以停止循环，还有一种情况就是该结点就是最小值，那么它就会到这个堆的堆顶去，即当前节点的下标为1时也要停止循环。
void up(int x){
while(x/2 || h[x/2] > h[x]){
heap_swap(x,x/2);
x >>= 1;
}
}
下沉（参数是元素在堆中的下标）
同理，如果一个结点值比他的子节点要大，他就要下沉，由于子节点有两个-左右儿子，因此需要比较与子节点的大小，如果满足条件就先堆交换在下沉，不断下沉直至到达合适的位置，当然要是不满足条件就不必下沉。
void down(int x){
int t = x;
if(2*x <= cnt && h[2*x] < h[t]) t=x*2;
if(2*x+1 <= cnt && h[2*x+1] < h[x]) t=2*x+1;
if(x!=t){
heap_swap(x,t);
down(t);
}
}
堆交换（参数是元素在堆中的下标）
对于x，y两个数，首先要知道他们当前在堆中的下标a,b然后才能heap_swap(a,b)，那么怎么交换这两个数在堆中的位置呢。
首先就得要知道他们什么时候进来的hp[a],hp[b]，交换这个顺序在堆中存储的下标swap(ph[hp[a]],ph[hp[b]])。
然后交换他们进来的先后顺序swap(hp[a],hp[b])。
最后在交换在堆中的值swap(h[a],h[b])。
void heap_swap(int a,int b){
swap(ph[hp[a]],ph[hp[b]]);
swap(hp[a],hp[b]);
swap(h[a],h[b]);
}
代码实现
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1000010;
int h[N]; // 存储堆的值
int hp[N]; // 下标为a所对应的数--表示一种顺序
int ph[N]; // 第k个数所对应的下标a--指针
int cnt,m; // 最后一个数
// 交换三组:
// 1.对这两个数的下标所对应的顺序值，第几个值(顺序值)在堆中所对应的下标进行交换
// 2.先交换存储在ph中某两个相对(插入的顺序)的数所指向堆中的下标
// 3.最后交换a，b这两个位置的值
void heap_swap(int a,int b){
swap(ph[hp[a]],ph[hp[b]]);
swap(hp[a],hp[b]);
swap(h[a],h[b]);
}
void down(int x){
int t = x;
if(x * 2 <= cnt && h[2*x] < h[t]) t = 2*x;
if(x * 2 + 1 <= cnt && h[2*x + 1] < h[t]) t = 2*x+1;
if(x != t){
heap_swap(x,t); // 交换x，t，与堆排序的不同，这里使用的是heap_swap,只需要提供下标，再函数内部堆下标所指向的数及进行排序
down(t);
}
}
void up(int x){
while(x / 2 && h[x/2] > h[x]){ // x/2
heap_swap(x,x/2);
x >>= 1;
}
}
int main()
{
int n;
cin >> n;
while(n--){
string op;
int x,k;
cin >> op;
if(op == "I"){
cin >> x;
++cnt,++m;
h[cnt] = x; // cnt所对应存储在堆h中的值
ph[m] = cnt,hp[cnt] = m; // cnt是下标，m是第几个数，都从1开始
up(cnt); // 插入位置的元素上浮
}
else if(op == "D"){ // 删除：删除第k个数，那就拿最后一个数覆盖他，然后对这个数调整
cin >> k;
k = ph[k];
heap_swap(k,cnt);
cnt--;
up(k); // 不管交换后最后一个的值是大还是小，都先上浮或下浮一遍.
down(k);
}
else if(op == "C"){
cin >> k >> x;
k = ph[k]; // 找到第k数所对应的下标
h[k] = x; // 将对应的位置修改值
up(k); // 调整修改后的数的位置
down(k);
}
else if(op == "PM"){
cout << h[1] << endl;
continue;
}
else{ // "DM"删除最小值
heap_swap(1,cnt);
cnt--;
down(1); // 只能向下调整
}
}
return 0;
}