四、堆例题——堆排序
题目描述
输入一个长度为 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; }