数据结构：手撕堆和哈希表，字符串哈希详解----小白也能懂

堆

如何手写一个堆？

1，插入一个数

2，求集合当中的最小值

3，删除最小值

4，删除任意一个元素

5，修改任意一个元素

堆的结构：是一个完全二叉树（除了最后一层节点，其余节点都是非空的，最后一层是从左到右依次排布的

小根堆：每个根都是小于他的两个子节点的

大根堆：每个根都是大于他的两个子节点的

最后的两个例题必须看，很重要

堆的存储

凡是堆状，完全二叉树都是这样存的，拿一个数组存储

图大概就长这样

堆有两个基本操作

这两个操作完全可以组合，然后把上面提到的五个操作完成

1，down( x )

是把一个节点往下移，就比如下面这个图，我们找到不合适的位置，然后对他进行down，我们找到自己系欸但最小的那个进行交换

void down(int u){ //u是索引哈，是第几个节点,h[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){ swap(h[u], h[t]); down(t); } }

2 , up( x )

和down反着来，同理就行

void up (int u){ //看父节点就行了 while(u / 2 && h[u / 2] > h[u]) { swap(h[u/2], h[u]); u/=2; } }

操作一：插入一个数

我们用size表示堆的大小，heap表示我们这个堆

heap[ ++ size] = x ; up(size);我们就是在堆的最后一个位置插入x，然后进行上移

操作二：求集合中的最小值

heap [ 1 ]就行

操作三：删除最小值

这个需要一点点的技巧，我们让最后一个元素覆盖到堆顶去，之后size--，就行了，然后我们再down一遍，这不就删了最小值嘛。潇洒！！！

heap[ 1 ] = heap [ size ] ; size -- ; down[ 1 ];

操作四：删除任意一个元素

heap [ k ] = heap [size] ; size --;

这个需要判断一下这个值是变大还是变小，变大就down，变小就up

或者不判断，无外乎三种情况，我们不管三七二十一，就直接down ，up

操作五：修改任意一个元素

heap[ k ] = x; down( k ) ; up( k );

这个我们也不管三七二十一就直接down，up就行

题目模板练习1

这个模板就是最普通的堆模板

这里的建堆操作是O( n )的，因为我们从n/2开始也就是倒数第二层开始，然后对他们每一层建自己的堆，然后 i--每次都建堆，然后我们可以得到式子，n / 2 * 1 + n / 4 * 2 + n / 8 * 3 + ....... 最后算出就一定是小于 n 的时间复杂度

#include<iostream> using namespace std; const int N = 1e5 + 10; int sizes, n, m; int h[N]; void down(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); } } //void up (int u){ // //看父节点就行了 // while(u / 2 && h[u / 2] > h[u]) { // swap(h[u/2], h[u]); // u/=2; // } //} int main(){ 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

这里来分析一下，我们现在要找到第k个插入的点，现在在堆里面哪个下标（ph的作用)，那我们的h[]交换后，那我们是不是就找不到想找到的那个数了，我们还需要一个hp数组来记录交换后的h[]，对应的下标是第几个插入的数

sizes 是堆里面最开始的下标记录变量，然后++就记录堆里面的元素对应的下标

m记录当前扔进堆里面的数是第几个插入的

ph[ m ] = sizes意思就是得到了第m个插入的元素是在堆里面sizes位置

hp[ sizes ] = m意思是堆里面sizes这个位置的数是第m个插入的数

然后当发生了down或者up操作出现需要交换节点，那我们的h [ a ] , h[ b ]这个代表堆里面ab位置的值，这个肯定要交换，那堆里面a位置是第几个插入的数，和b位置是第几个插入的数，这两个也是要交换的（hp），那我们肯定要知道第几个插入的数是在哪个位置（ph)，这个值也是要交换的（ph）

然后到后面我们需要修改第k个插入的数，那我们首先要找到第k个插入的数现在在堆里面那个位置也就是ph是多少，那我们需要这个

 sizes ++;//d堆里面多一个元素 m ++;//第m个插入的数 ph[m] = sizes;//最开始第m个插入的数是在sizes节点位置的 hp[sizes] = m;//sizes节点位置是第m个插入的数 h[sizes] = x;

#include<iostream> #include<string.h> using namespace std; const int N = 1e5 + 10; int sizes, n, m; int h[N], ph[N], hp[N];//ph[k]存的是第k个插入的点是哪个点，他在堆里是哪个点 //hp [k]堆里面某个点是第几个插入的点 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 <= 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); } } void up (int u){ //看父节点就行了 while(u / 2 && h[u / 2] > h[u]) { heap_swap(u / 2, u); u/=2; } } int main(){ 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); } else if(!strcmp(op,"PM")) printf("%d\n", h[1]); else if(!strcmp(op,"DM")) { heap_swap(1,sizes); sizes--; down(1); } else if(!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); } } }

总结：

可能就是第二个例题是有点难的，他用了俩额外数组映射，但其实我们是很少用到他的，我们只要掌握那几个基础操作就行，但是Dijkstra算法中我们经常会用到这个堆，还有一点是，我上面所写的都是以小根堆为例子的

哈希表

我们要介绍两大块

1，存储结构：开放寻址法，拉链法

2，字符串哈希方式：

用到哈希表的情况：他最主要的作用就是，把一个非常大的值域映射到一个比较小的区域

就是从0到N的区域

常见的一种情景：我们把0到1e9的数映射到----》》0到1e5的一些数也就是mod 1e5

哈希函数：h( x ) 他的作用就是让，比如有-1e9到1e9我们把他们映射成1e5的数

冲突：映射过程中我们会出现冲突，因为你mod后肯定会有相同值，这时候我们就要用上面提到的两种存储结构来解决了(我们mod的这个数要去为质数，而且要离2的整次幂)

存储结构：拉链法

开一个数组从下标0到1e5，有重复的数，我们就拉一个链子在下面接着

在算法题里面，我们一般只有添加和查找操作，没有删除操作

添加x，我们就看一下h( x )是多少，就把这个接到下面就行

查找x，就看一下h(x)在哪个槽里面，然后我们遍历一下这个链表

如果说要删除，我们也不会真的删除，只是在这个节点打一个标记（bool）

模板在下面

#include<iostream> #include<cstring> using namespace std; const int N = 1e5 +3; int h[N], e[N], ne[N], idx; void insert(int x){ int k = (x % N + N) % N;//如果是负数就变成正数 //这里是头插法，然后h[k]就相当于头节点了 e[idx] = x; ne[idx] = h[k]; h[k] =idx ++; } bool find(int x){ int k = (x % N + N) % N; for(int i = h[k]; i != -1; i =ne[i]){ if(e[i] == x){ return true; } } return false ; } int main(){ int n; scanf("%d", &n); memset(h, -1, sizeof(h)); while(n --){ char op[2]; int x; scanf("%s%d", op, &x); if(*op == 'I') insert(x); else{ if(find(x)) puts("Yes"); else{ puts("No"); } } } }

存储结构：开放寻址法

处理冲突思路：

他就开了一个一维数组，没有用链表，但他数组一般开为要求的最大长度的2或3倍

假设我们的h( x ) = k;我们就去看看这个位置有没有人，如果有人的话，我们就去下一个位置，就是我们从k位置去看，如果有人，就一直往后找，知道找到为空的，给他插进去

查找

也从第k个位置开始，从前往后找，看看找的位置又有没有人，有人就一直往后找，就一直找

如果找到某一个位置没人，就说明没有这个数

删除

我们就标记一下x就行，不是真的删除，我们一般不用删除操作

模板在这，它的核心就是这个find函数

我们从k位置开始往后找，如果这个位置不为空( h[k ] != null）同时这个位置不是要找的x（h[k] != x），那就k++继续往后找，如果找到最后一个位置N，那就返回到0继续找

int find (int x){ int k = (x % N + N) % N; while(h[k] != null && h[k] !=x){ k ++; if(k == N) k =0;//从k看完看到N后都不是x就从0再看 } return k; }

#include<iostream> #include<cstring> using namespace std; const int N = 2e5 +3, null = 0x3f3f3f3f; int h[N], e[N], ne[N], idx; int find (int x){ int k = (x % N + N) % N; while(h[k] != null && h[k] !=x){ k ++; if(k == N) k =0;//从k看完看到N后都不是x就从0再看 } return k; } int main(){ int n; scanf("%d", &n); //每个位置初始化为一个不可能的值 memset(h, 0x3f, sizeof(h)); //这里是0x3f因为memset是按字节赋值，我们的int是4个字节，那一个字节是0x3f,那四个就是0x3f3f3f3f while(n --){ char op[2]; int x; scanf("%s%d", op, &x); int k = find(x); if(*op == 'I'){ h[k] = x; } else{ if(h[k] != null) puts("Yes"); else{ puts("No"); } } } }

总结

这两个存储方式都是可以的，没有好坏之分

字符串哈希

我们用的方法是字符串前缀哈希法

比如 str=“abcabcdeyxc"

h[0] = 0;

h[1] = “a"的哈希值

h[2] = "ab"的哈希值

h[3] = "abc"的哈希值

h[4] = "abca"的哈希值

那么我们如何求出哈希值呢

1，p进制，我们把这个字符串看成是一个p进制的数，字母（ascll）就表示p进制的每一位数字，听着比较抽象，我举个例子

（a，b，c，e）p进制形式 --》转为十进制就是（1 * p^3 + 2 * p^2 + 3 * p^1 + 5 * p^0)

由于我们的字符串可能很长很长，那我们的值就会很大很大，这时候我们会用一个比较小的Q，让他们mod Q，这样就映射到了1 --- Q - 1的位置了

注意：

1，一般情况下我们不能把数映射成数字0

2，还有就是前面我们的哈希存储方式，都有一种解决冲突的方法，但我们字符串哈希这里没有，我们假定我们人品足够好，不存在冲突。

当p = 131或13331时，我们的Q取2^64，这样取的话，我们99.9999%情况都不会发生冲突

预处理字符串的前缀值

我们不再mod 2^64因为我们直接用unsigned long long来取值，如果溢出的话，就直接相当于mod 2^64l1

 for(int i = 1; i <= n; i++){ p[i] = p[i -1] * P; h[i] = h[i - 1] * P +str[i]; }

怎么获得想要的哈希值

完整代码在这

#include<iostream> using namespace std; typedef unsigned long long ULL; const int N =1e5 +10, P =131; int n, m; char str[N]; ULL h[N], p[N]; ULL get(int l, int r){ return h[r] - h[l - 1]*p[r - l + 1]; } int main(){ scanf("%d%d%s", &n, &m, str + 1); p[0] = 1; for(int i = 1; i <= n; i++){ p[i] = p[i -1] * P; h[i] = h[i - 1] * P +str[i]; } while(m --){ int l1, r1, l2, r2; scanf("%d%d%d%d", &l1, &r1, &l2, &r2); if(get(l1, r1) == get(l2, r2)) puts("Yes"); else puts("No"); } return 0; }

字符串哈希其实很好用，kmp有时候都得退步三分

到此完结了，总算是写完了，球球给个三连吧，码字不易，做图也不不易