四、堆例题——堆排序
题目描述
输入一个长度为 n 的整数数列，从小到大输出前 m 小的数。
输入格式
第一行包含整数 n 和 m。
第二行包含 n 个整数，表示整数数列。
输出格式
共一行，包含 m 个整数，表示整数数列中前 m 小的数。
数据范围
1 ≤ m ≤ n ≤ 1e5
1 ≤ 数列中元素 ≤ 1e9
输入样例
5 3
4 5 1 3 2
输出样例
1 2 3
具体实现
1. 实现思路
- 见上面堆排序讲解。
2. 代码注解
h[N] 就是堆（heap）。
size 是当前堆（heap）当中有多少个元素。
在 C++ 当中，如果有的头文件包含了一个变量或者函数，这是我们再次定义调用的话，会产生模糊报错，即 reference to ‘size’ is ambiguous ，我们只需要对变量或者函数改一个名字即可。
3. 实现代码
#include <bits/stdc++.h> using namespace std; const int N=100010; int n,m; int h[N],ssize; void down(int u)//比较三个数当中的最小值 { int t=u; //左子节点 （左子节点存在且左子节点小于父节点） if(u*2 <= ssize && h[u*2]<h[t]) { t=u*2; } //右子节点 （右子节点存在且右子节点小于父节点） if(u*2+1 <= ssize && h[u*2+1]<h[t]) { t=u*2+1; } if(u!=t) { swap(h[u],h[t]); down(t); } } int main() { cin>>n>>m; for(int i=1;i<=n;i++) { cin>>h[i]; } ssize=n; for(int i=n/2;i!=0;i--) { down(i); } while(m--) { cout<<h[1]<<" "; h[1]=h[ssize]; ssize--; down(1); } system("pause"); return 0; }
五、堆例题——模拟堆
题目描述
维护一个集合，初始时集合为空，支持如下几种操作：
（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 ≤ N ≤ 1e5
−1e9 ≤ x ≤ 1e9
数据保证合法。
输入样例
8
I -10
PM
I -10
D 1
C 2 8
I 6
PM
输出样例
-10
6
具体实现
1. 代码注解
h[N] 就是堆（heap）。
cnt 是当前堆（heap）当中有多少个元素。
ph[k] = x 表示第 k 个插入的元素在堆中存放的位置是 x 。
此时如果要交换 ph 中的两个元素需要知道堆中位置 x 是第几个被插入的, 于是便引入了数组 hp 。
hp[x] = k 表示堆中位置 x 存放的为第 k 个插入的元素，与 ph[k] = x 互为反函数，一 一对应。
2. 实现代码
#include <bits/stdc++.h> using namespace std; const int N = 100010; int h[N],cnt; int ph[N],hp[N]; 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<=cnt&&h[u*2]<h[t]) { t=u*2; } if(u*2+1<=cnt&&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; } } int main() { int n, m = 0; cin>>n; while (n--) { char op[5]; int k, x; cin>>op; if (!strcmp(op, "I")) { cin>>x; cnt++ ; m++; ph[m]=cnt; hp[cnt]= m; h[cnt]=x; up(cnt); } else if(!strcmp(op,"PM")) { cout<<h[1]<<endl; } else if(!strcmp(op,"DM")) { heap_swap(1,cnt); cnt-- ; down(1); } else if(!strcmp(op,"D")) { cin>>k; k=ph[k]; heap_swap(k,cnt); cnt-- ; up(k); down(k); } else { cin>>k>>x; k=ph[k]; h[k]=x; up(k); down(k); } } system("pause"); return 0; }
