文章目录
- 算法模板
- 堆题目代码模板
- 堆的原理
- down操作理解：
- up操作理解
- 建堆操作
- 关于heap_swap中存的映射数组理解（模拟堆题目中用到）
- 模板题
- 堆排序
- 原题链接
- 题目
- 思路
- 题解
- 模拟堆
- 原题链接
- 题目
- 思路
- 题解
算法模板
堆题目代码模板
// 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;
}
