二、数据结构10：堆 模板题+算法模板（堆排序，模拟堆）

算法模板

堆题目代码模板

// h[N]存储堆中的值, h[1]是堆顶，x的左儿子是2x, 右儿子是2x + 1
// ph[k]存储第k个插入的点在堆中的位置
// hp[k]存储堆中下标是k的点是第几个插入的
int h[N], ph[N], hp[N], size;// 交换两个点，及其映射关系
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 u)
{int t = u;if (u * 2 <= size && h[u * 2] < h[t]) t = u * 2;if (u * 2 + 1 <= size && h[u * 2 + 1] < h[t]) t = u * 2 + 1;if (u != t){heap_swap(u, t);down(t);}
}void up(int u)
{while (u / 2 && h[u] < h[u / 2]){heap_swap(u, u / 2);u >>= 1;}
}// O(n)建堆
for (int i = n / 2; i; i -- ) down(i);

堆的原理

以小根堆为例，小根堆中每个点小于等于左右儿子是递归定义的，

down操作理解：

down完后：

代码实现：

up操作理解

up完后：

各种操作的实现思路：

建堆操作

建堆：一个一个插时间复杂度为O(nlogn)
使用上图中该方法从n/2 down到1，时间复杂度为O(n)

关于heap_swap中存的映射数组理解（模拟堆题目中用到）

由于该题目中需要对“第k个插入”的数进行处理，因此需要存两个数组来知道“第k个插入”的数在堆数组中的下标位置，在交换操作时也需要交换对应的映射。

ph[j]:第j个插入的点在堆数组中下标为k
hp[k]:堆里面下标为j的点对应的ph数组中的下标为j

模板题

堆排序

原题链接

https://www.acwing.com/problem/content/840/

题目

输入一个长度为 n
的整数数列，从小到大输出前 m
小的数。

输入格式
第一行包含整数 n
和 m
。

第二行包含 n
个整数，表示整数数列。

输出格式
共一行，包含 m
个整数，表示整数数列中前 m
小的数。

数据范围
1≤m≤n≤105
，
1≤数列中元素≤109
输入样例：

5 3
4 5 1 3 2

输出样例：

1 2 3

思路

建堆+down操作维护堆+删除堆顶元素操作，每次输出堆顶（h[1]）即为当前最小值

题解

#include <iostream>
#include <algorithm>
using namespace std;const int N = 1e5 + 10, M = 1e5 + 10;
int h[N];
int n,m;
int sizeOfH;void down(int u){int t = u;if(u*2 <= sizeOfH && h[u*2]<h[t]) t = u*2;if(u*2+1 <= sizeOfH && h[u*2+1] < h[t]) t = u*2+1;if(u!=t){swap(h[t],h[u]);down(t);}} 
int main(){cin>>n>>m;for(int i=1;i<=n;i++) cin>>h[i];sizeOfH = n;//	建堆 for(int i=n/2; i ; i--) down(i);while(m--){printf("%d ",h[1]);h[1] = h[sizeOfH];sizeOfH--;down(1);}} 

模拟堆

原题链接

https://www.acwing.com/problem/content/841/

题目

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

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

思路

实现堆的基本操作，但要注意的是题目中需要对“第k个插入”的数进行处理，因此需要维护ph和hp两个映射数组，并使用自定义的heap_swap方法。

题解

#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;const int N = 1e5 +10;int h[N],ph[N],hp[N],sizeOfH;
int n;void heap_swap(int a,int b){//因为操作中需要对“第k个插入”的数进行删除和修改操作，因此需要使用映射版的swap swap(ph[hp[a]],ph[hp[b]]);//ph[j]:第j个插入的点在堆数组中下标为k，hp[k]:堆里面下标为j的点对应的ph数组中的下标为j swap(hp[a],hp[b]);swap(h[a],h[b]);
}void down(int u){int t = u;if(u*2 <= sizeOfH && h[u*2]<h[t]) t = u*2;if(u*2+1 <= sizeOfH && h[u*2+1]<h[t]) t = u*2+1;if(t != u){heap_swap(t,u);down(t);}
}void up(int u){while(u/2 && h[u/2] > h[u]){ // 如果其父节点比该节点大，则将该节点up heap_swap(u/2,u);u/=2;}
}int main(){int m=0; // 全局中递增的唯一id 记录是第几个插入的数 cin>>n;while(n--){char op[10];int k,x;scanf("%s",op); // cin>>op;if(!strcmp(op,"I")){ //strcmp(const char *str1, const char *str2) 如果返回值小于 0，则表示 str1 小于 str2。如果返回值大于 0，则表示 str1 大于 str2。如果返回值等于 0，则表示 str1 等于 str2。cin>>x;sizeOfH++;m++;h[sizeOfH] = x;ph[m] = sizeOfH;hp[sizeOfH] = m;up(sizeOfH);} else if(!strcmp(op,"PM")) printf("%d\n",h[1]);else if(!strcmp(op,"DM")) {heap_swap(1,sizeOfH);sizeOfH--;down(1);}else if(!strcmp(op,"D")){cin>>k;k = ph[k];  // 找到第k个插入的数在堆数组中的坐标heap_swap(k,sizeOfH);sizeOfH--;down(k); // down和up其实只有其中一个起作用，但方便起见这样写 up(k);}else{cin>>k>>x;k = ph[k]; // 找到第k个插入的数在堆数组中的坐标h[k] = x;down(k);up(k);}}return 0; 
}