这个模板就是最普通的堆模板。
这里的建堆操作是 O(n) 的,因为我们从 n/2 开始也就是倒数第二层开始,然后对他们每一层建自己的堆,然后 i--每次都建堆,然后我们可以得到式子,n / 2 * 1 + n / 4 * 2 + n / 8 * 3 + ....... 最后算出就一定是小于 n 的时间复杂度。
#include<iostream>usingnamespace std;
constint N = 1e5 + 10;
int sizes, n, m;
int h[N];
voiddown(int u){
int t = u;
if(u * 2 <= sizes && h[u * 2] < h[t]) t = u * 2;
if(u * 2 + 1 <= sizes && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
if(u != t){
swap(h[u], h[t]);
down(t);
}
}
intmain(){
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) scanf("%d", &h[i]);
sizes = n;
//建堆for(int i = n / 2; i; i --) down(i);
while(m --){
printf("%d ", h[1]); //输出前 m 个最小值
h[1] = h[sizes];
sizes --;
down(1);
}
}
题目模板练习二
这个是常常用在 Dijkstra 算法中的堆模板。
需要注意的是,操作 4 是让你删除第 k 个插入的数,还有操作 5 修改第 k 个插入的数,他们说的是第 k 个插入的,而不是删除某个节点,所以我们还需两个数组来记录插入顺序。
主要是要知道这两个数组的含义,hp[i] = k 数组记录的是第 i 个点是第 k 个插入的数,ph[k] = i 意思是第 k 个插入的数的节点是 i。
sizes 是堆里面最开始的下标记录变量,然后++就记录堆里面的元素对应的下标。
m 记录当前扔进堆里面的数是第几个插入的。
ph[m] = sizes 意思就是得到了第 m 个插入的元素是在堆里面 sizes 位置。
hp[sizes] = m 意思是堆里面 sizes 这个位置的数是第 m 个插入的数。
当发生了 down 或者 up 操作出现需要交换节点,那我们的 h[a], h[b] 这个代表堆里面 ab 位置的值,这个肯定要交换,那堆里面 a 位置是第几个插入的数,和 b 位置是第几个插入的数,这两个也是要交换的(hp),那我们肯定要知道第几个插入的数是在哪个位置(ph),这个值也是要交换的(ph)。
#include<iostream>#include<string.h>usingnamespace std;
constint N = 1e5 + 10;
int sizes, n, m;
int h[N], ph[N], hp[N];
//ph[k] 存的是第 k 个插入的点是哪个点,他在堆里是哪个点//hp [k] 堆里面某个点是第几个插入的点voidheap_swap(int a, int b){
swap(ph[hp[a]], ph[hp[b]]);
swap(hp[a], hp[b]);
swap(h[a], h[b]);
}
voiddown(int u){
int t = u;
if(u * 2 <= sizes && h[u * 2] < h[t]) t = u * 2;
if(u * 2 + 1 <= sizes && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
if(u != t){
heap_swap(u, t);
down(t);
}
}
voidup(int u){
while(u / 2 && h[u / 2] > h[u]) {
heap_swap(u / 2, u);
u/=2;
}
}
intmain(){
scanf("%d", &n);
while(n --){
char op[10];
int k, x;
scanf("%s", op);
if(!strcmp(op,"I")){
scanf("%d", &x);
sizes ++;//d 堆里面多一个元素
m ++;//第 m 个插入的数
ph[m] = sizes;//最开始第 m 个插入的数是在 sizes 节点位置的
hp[sizes] = m;//sizes 节点位置是第 m 个插入的数
h[sizes] = x;
up(sizes);
} elseif(!strcmp(op,"PM")) printf("%d\n", h[1]);
elseif(!strcmp(op,"DM")) {
heap_swap(1,sizes);
sizes--;
down(1);
} elseif(!strcmp(op,"D")){
scanf("%d", &k);
k = ph[k];//找到第 k 个插入的元素是哪个点heap_swap(k, sizes);
sizes --;
down(k),up(k);
} else{
scanf("%d%d", &k, &x);
k = ph[k];
h[k] = x;
down(k), up(k);
}
}
}
哈希表
我们要介绍两大块:
存储结构:开放寻址法,拉链法
字符串哈希方式
用到哈希表的情况:它最主要的作用就是,把一个非常大的值域映射到一个比较小的区域,就是从 0 到 N 的区域。
常见的一种情景:我们把 0 到 1e9 的数 映射到 0 到 1e5 的一些数 也就是 mod 1e5。
哈希函数:h(x) 他的作用就是让,比如有 -1e9 到 1e9 我们把他们映射成 1e5 的数。
冲突:映射过程中我们会出现冲突,因为你 mod 后肯定会有相同值,这时候我们就要用上面提到的两种存储结构来解决了 (我们 mod 的这个数要去为质数,而且要离 2 的整次幂)。