acwing算法笔记-数据结构：Trie树和堆

Trie树

Trie树是一个字典树，它可以高效的存储和查找字符串集合
高效的原因：空间换时间，利用字符字符串的公共前缀来降低查询时间的开销来提高效率
应用场景：统计和排序大量的字符串
- 文本词频
- 前缀匹配
- 字符串检索
时间复杂度：insert和query均为$O(n)$
空间复杂度：存储了一棵树，非常庞大如果是英文小写字母$O(26^n)$

835. Trie字符串统计

基本思路

根据题意需要实现两个函数，insert和query。
这里是用数组模拟Trie树，Trie树本质就是一个多叉树，我们用邻接表去模拟（链表基础）

图论的题目直接结合代码分析会更直接

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>

using namespace std;

const int N = 100010;

//0号点既是根节点，又是空节点
// son[][]存储树中每个节点的子节点,一维是当前节点，二维是边（也就是子节点的值），结果是子节点
// cnt[]存储以每个节点结尾的单词数量
int son[N][26], cnt[N], idx;  
char str[N];

void insert(char *str)
{
    int p = 0;     //p指向根节点
    for (int i = 0; str[i]; i ++ )  //未到\0一直insert
    {
        int u = str[i] - 'a';                 //找到边，也就是子节点的值
        if (!son[p][u]) son[p][u] = ++ idx;   //p节点不存在u这个儿子的话，就创建出来
        p = son[p][u];                        //p指针移动到子节点
    }
    cnt[p] ++ ;
}

int query(char *str)
{
    int p = 0;
    for (int i = 0; str[i]; i ++ )
    {
        int u = str[i] - 'a';
        if (!son[p][u]) return 0;
        p = son[p][u];
    }
    return cnt[p];
}

int main()
{
    int n;
    scanf("%d", &n);
    while (n -- )
    {
        char op[2];
        scanf("%s%s", op, str);
        if (*op == 'I') insert(str);
        else printf("%d\n", query(str));
    }

    return 0;
}

Reference

[1]. yxc
[2]. 图文结合的超详细解析
[3]. 详细注释
[4]. 如何理解单(双)链表，Trie树和堆中的idx？
[5]. 应用场景


堆

堆是一种集合，它实质上是一个满足堆性质的完全二叉树。
首先什么是完全二叉树，那就是最后一层上面的是满二叉树（最后一层节点从左到右排列）

堆又分为大根堆和小根堆
如果对于任意一个节点，它的值都大于等于左右节点，那就是大根堆，因为堆顶是最大值
同理如果对于任意一个节点，它的值都小于等于左右节点，那就是小根堆，因为堆顶是最小值

那么对于一个堆，我们通常需要实现几个操作

  1. 插入
  2. 拿到堆顶节点的值
  3. 删除堆顶
  4. 删除任意一个节点
  5. 修改任意一个节点

下面两道模板提可以详细地去探究如何实现这些操作

注意堆的话下标从1开始更方便，因为左右节点我们分别是用2x和2x+1表示，如果从0开始就需要特判，所以从1开始就可以省去

838. 堆排序

基本思路

要求我们堆排序，并且是升序。
所以我们可以构建一个小根堆。每次拿到堆顶，输出，然后删除堆顶，循环之前的操作，我们就可以得到一个升序的排序。

注意：

  1. down操作，左右儿子需要满足堆的性质，所以如果用down建堆的时候需要从n/2开始，也就是最后一个叶节点的父节点开始
  2. up操作，父节点需要满足堆的性质，所以从根节点开始

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int n, m;
int h[N], cnt;  //h[]存储节点值， cnt就是堆的size

//堆的down操作
void down(int u)
{
    int t = u;  //t是最小值节点
    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)    //如果当前节点不是最小值节点，那就交换数值
    {
        swap(h[u], h[t]);
        down(t);   //调整后u节点肯定满足堆性质，但是t节点可能不满足，所以递归调用直到满足
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &h[i]);
    cnt = n;

    for (int i = n / 2; i; i -- ) down(i);   //构建小根堆，把元素存入

    while (m -- )
    {
        printf("%d ", h[1]);
        h[1] = h[cnt -- ];
        down(1);
    }

    puts("");

    return 0;
}

Reference

[1]. yxc
[2]. Bug-Free
[3]. 详细注释
[4]. 分析i=n/2
[5]. 堆排序—完整注释


839. 模拟堆

基本思路

模板题，模拟堆的基本操作，这里需要注意的一点是，我们删除和修改是针对第k个插入的数（这里的k不是节点下标）
这里详细探讨一下用到的变量

首先我们知道 节点 由节点值和节点地址构成 （用节点地址访问节点的节点值）
这里使用数组模拟节点，所以用下标表示节点地址。idx表示的是当前用到第几个节点，一定唯一，相当于是节点的ID。
在链表中，节点之间的关系我们用ne[]维护，所以节点对应的下标是不会改变的（idx映射到下标的关系不会更改），我们可以让idx = 下标
但是在二叉树结构中（例如堆）节点之间的关系我们是用下标维护的，所以节点对应的下标是会改变的（idx映射到下标的关系会改变），我们就需要建立两个映射数组，维护idx和下标的映射

所以在堆中，需要建立两个映射数组，ph[]将idx映射到下标，hp[]将下标映射到idx

弄清楚这些变量之后，我们再看heap_swap的操作
两个节点交换位置 = idx交换(hp[])，节点下标交换(ph[])，节点值交换(h[])

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <iostream>
#include <algorithm>
#include <string.h>

using namespace std;

const int N = 100010;

int h[N], ph[N], hp[N], cnt;

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, idx = 0;    //第idx次插入
    scanf("%d", &n);
    while (n -- )
    {
        char op[5];
        int k, x;
        scanf("%s", op);
        if (!strcmp(op, "I"))
        {
            scanf("%d", &x);
            cnt ++ ;  //堆的大小+1
            idx ++ ;  //插入+1
            ph[idx] = cnt, hp[cnt] = idx;  //每次插入都是在堆尾插入（设置ph与hp）
            h[cnt] = x;  //堆中元素赋值
            up(cnt);
        }
        else if (!strcmp(op, "PM")) printf("%d\n", h[1]);
        else if (!strcmp(op, "DM"))
        {
            heap_swap(1, cnt);
            cnt -- ;
            down(1);
        }
        else if (!strcmp(op, "D"))
        {
            scanf("%d", &k);
            k = ph[k];   // 通过ph[ ]数组由k索引到它在堆中的下标，然后进行操作
            heap_swap(k, cnt);
            cnt -- ;
            up(k);    // 交换完，可能会变大、也可能变小，down和up各一遍，两个操作只有一个会支持
            down(k);
        }
        else
        {
            scanf("%d%d", &k, &x);
            k = ph[k];   
            h[k] = x;   // 修改任意元素
            up(k);
            down(k);
        }
    }

    return 0;
}

Reference

[1]. yxc
[2]. Bug-Free
[3]. 如何理解模拟堆中的heap_swap，hp[N], ph[N]？
[4]. 模拟堆概述


算法 > AcWing
#算法 #数据结构
acwing算法笔记-数据结构：Trie树和堆
https://vendestine.com/trie-heap
Author
Wenzhe Li
Posted on
April 15, 2022
Licensed under