吕梁市住房与城乡建设厅网站,视频教程网,wordpress比织梦好,邹城做网站文章目录 算法模板堆题目代码模板堆的原理down操作理解#xff1a;up操作理解建堆操作关于heap_swap中存的映射数组理解#xff08;模拟堆题目中用到#xff09; 模板题堆排序原题链接题目思路题解 模拟堆原题链接题目思路题解 算法模板
堆题目代码模板
// h[N]存储堆中的… 文章目录 算法模板堆题目代码模板堆的原理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*21 sizeOfH h[u*21] h[t]) t u*21;if(u!t){swap(h[t],h[u]);down(t);}}
int main(){cinnm;for(int i1;in;i) cinh[i];sizeOfH n;// 建堆 for(int in/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 xPMDMD 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个插入的点在堆数组中下标为khp[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*21 sizeOfH h[u*21]h[t]) t u*21;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 m0; // 全局中递增的唯一id 记录是第几个插入的数 cinn;while(n--){char op[10];int k,x;scanf(%s,op); // cinop;if(!strcmp(op,I)){ //strcmp(const char *str1, const char *str2) 如果返回值小于 0则表示 str1 小于 str2。如果返回值大于 0则表示 str1 大于 str2。如果返回值等于 0则表示 str1 等于 str2。cinx;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)){cink;k ph[k]; // 找到第k个插入的数在堆数组中的坐标heap_swap(k,sizeOfH);sizeOfH--;down(k); // down和up其实只有其中一个起作用但方便起见这样写 up(k);}else{cinkx;k ph[k]; // 找到第k个插入的数在堆数组中的坐标h[k] x;down(k);up(k);}}return 0;
}
