数据结构与算法

这是我大二上修的《数据结构与算法》的笔记。

数据结构绪论

数据相关术语

数据：所有能被计算机识别的符号集合
数据元素：是数据（结构）中的一个个体（一个人出生日期的年、月、日）
数据项：是数据结构中讨论的最小单位（一个人的出生日期）
数据对象：具有相同性质的数据元素的集合（迷宫的每一个点）

数据结构相关术语

数据结构：带结构的数据元素的集合。全面的来说，$DS = (E, R, M)$，$E$、$R$、$M$ 分别为数据元素（Element）的集合、数据元素之间关系（Relation）的集合、存储（Memorizaion）数据元素单位的集合。
逻辑结构：线性结构、树形结构、图形结构、集合结构。

存储结构：顺序存储、链式存储

操作：查找、插入、删除、遍历、排序……

数据类型相关术语

抽象数据类型（Abstract Data Type, ADT）：$ADT=(E,R,O)$。$O$ 指元素基本操作（Operation）的集合。

ADT 特点：抽象性（把定义和实现分开）、扩展性

算法相关术语

算法：解决某一特定问题的具体步骤的描述，是指令的有限序列。

算法是有穷的，通过有限步以后一定能得到输出；程序可以是无穷的，比如操作系统的核心进程，再启动完成后将驻留后台一直运行。

算法的五大基本性质：有穷性、确定性、可行性（能被分解为基本操作）、输入、输出。

算法设计的一般规则：正确性、可读性、健壮性（鲁棒性）、高效率和低存储量。

线性结构及其查找和排序

线性表相关术语

线性表下标从 1 开始。

头元素、尾元素；
前驱、后继、（直接）前驱、（直接）后继；

KMP （坑）

老师讲的 next[j] 指 p[0...j-1] s的（不包含自己）的 border 的长度。如：

p[j]	a	b	a	a	c	a	b	a	a
next[j]	-1	0	0	1	1	0	1	2	3

查找 Search

一些概念：

• ASL：平均查找长度。
• 静态查找：只做查询
• 动态查找：查到了删/没查到就插

顺序查找 Linear Search

网课的实现是在头插入所查找元素，然后从后往前查找。即带岗哨的顺序查找版本。这样的好处是 if 条件句能少一个条件。

等概率下：$ASL=\frac{n+1}{2}$；
不等概率下：可以把高概率的放在后面。

折半查找 Binary Search

需要有序表，并且只使用与顺序存储结构。

11 个数，等概率下：$ASL_{成功} = \frac{1}{11}(1 \times 1 + 2 \times 2 + 4 \times 3 + 4 \times 4) = 3$，
$ASL_{失败} = \frac{1}{12}(4 \times 3 + 8 \times 4) \approx 4$

$n>50$ 时，可认为 $ASL \approx log_2(n+1)-1$。

索引查找 Index Search

想一想字典的查找方法：有一个索引。

索引搜索的步骤：

1. 分析数据，建立索引

   (1) 对数据进行分块。须保证第 $R_k$ 块所有关键字 < $R_{k+1}$ 块所有关键字（块间有序）。

   (2) 然后建立索引线性表，每项存储了每块的首地址和最大关键字
   （注意最后一块后面也要存一个结束的查找表结束的地址，方便判断查找失败）

2. 查找
   (1) 索引表的查找（顺序或二分）
   (2) 查找表的查找（顺序或二分）

$
\begin{split}
\qquad ASL &= L_b+L_s \\
&= \frac{1}{b}\sum_{j=1}^b j + \frac{1}{s}\sum_{i=1}^s i \\
&= \frac{1}{2}(\frac{n}{s}+s)+1
\end{split}
$

哈希查找 Hash Search

哈希函数即是一个将任意一个东西映射到 $[0, n-1]$ 的整数区间上的一个函数。常用的映射规则有直接（对于整数）对 n 取模、（对于字符串）把字符串看做一个 26（或 32，加速乘法）进制的数，按转换为 10 进制的方法，转为数以后取模。

哈希查找即是把元素映射到 $[0, n]$ 后，把元素放在线性表对应下标的内存中，查找时，计算哈希函数，然后在对应内存的地方找。一般 $n$ 的选择是质数。

哈希函数是密码学相关的，所以这门课程没有讨论太多相关的内容，更多讨论的是哈希表解决冲突的方法。

定义装填因子为要存的元素个数/哈希表空间能存的元素个数。

$a = \frac {L.length()}{n}$

显然，装填因子小，冲突的可能性会变小。

做题时，给定 $a$，若计算的 $n$ 不是整数，应向上取整（保证 $a$ 变小）。

解决冲突的方法有：

1. 线性探测再散列（即存入数据时，如果发生冲突，则尝试将数据存入后 $d_1=1$ 个位子，如下标超出 n 则模 n。仍然冲突，则尝试存入原数据后 $d_2=2$ 个位子……直至数据被存下）
2. 平方探测再散列（${d_i} = {1^2, -1^2, 2^2, -2^2, …}$）
3. 随机数探测再散列（${d_i} = {7, 14, 21,…}$）
4. 链地址法（在哈希表的每一个内存外接链表）

常用方法 1 和 4。也有双哈希（即选择两个模数，然后建立两个一位数组作为哈希表，查找时若两表都查到了，就认为查找成功）等方法。

ASL 的计算需要计算每个数的查找次数（或冲突次数+1）。若查找失败，需要按 $d_i$ 一直找，直到该内存没有数据。

另外，删除数据时，需要注意，不能将该格还原为初始状态（如标记为 -1），否则某些后面的冲突项也会被忽略。
正确的是，进行特殊标记（如标记为 -2）。

排序 Sort

排序的稳定性

如果排序过程中，相同的数字的相对顺序可能变化，则称这个排序是不稳定的。

如快排，对于序列 $(3, \underline{3}, 2)$，排序以后是 $(2, \underline{3}, 3)$，两个 3 的相对位置，因此快排是不稳定的。

稳定的好处：一是交换的过程不会很混乱，在前面的依旧在前面；二是可以应用于基数排序；三是（感觉上）减少了交换的次数（因为两个一样大的数，把后面的数放到前面去，感觉做了无用功；实际也是稳定的更优秀）。

稳定的排序有：简单插入、冒泡排序、归并排序

不稳定的排序有：希尔排序、简单选择、快速排序

简单插入排序 Simple Insertion Sort

就是第 $i$ 趟保证前 $i$ 个数之间有序；为此，每次把第 $i$ 个元素插入到前 $i-1$ 个元素之间（慢在插入的过程需要移位）。如下序列跑三趟的结果是：

4 2 1 3
2 4 1 3
1 2 4 3
1 2 3 4

一般会使用第 0 位作为岗哨。

简单插入排序简单好写，并且在基本有序的表上表现很好：在有序表上只需要 $n-1$ 次比较和 0 次交换数据。交换数据的次数完全等于逆序对的个数。

希尔排序 Shell Sort

希尔排序是改进的简单插入排序。他将数据进行分组，然后进行排序，再把小组合为大组继续排序，以此类推。

如果把数据按分块的方式进行分组，对复杂度影响其实不大；有意思的是，如果是隔几个数分为一组（如123123123……），就会有神奇的效果：
一趟排序完成以后，每组基本都是有序的，整体来看也是小的在前，大的在后，这样，每趟就是基本有序的插入排序了，复杂度接近 $O(n)$。平均复杂度就得到了降低。

然而，希尔排序的最坏复杂度可以为 $\Theta(n^2)$，如构造以下数列：

1 9 2 10 3 11 4 12 5 13 6 14 7 15 8 16

按间隔 $d_i=\{8,4,2,1\}$ 的话，前三趟做的都是无用功，最后一趟实际等同于简单插入排序，复杂度为 $\Theta(n^2)$。（实际上 $\{8,2,4,1\}$ 就是 Shell 本人提出的序列）

上述的原因是，增量间不互质，于是小的增量可能没有效果。

接下来，就是讨论希尔排序的增量序列（和哈希函数一样，想在一个核心上做文章，取得整体的复杂度的改善）。

在说序列之前，贴一份希尔排序的参考代码（也可下载 sort.cpp）

//简单插入排序，但是带有 dist 参数，可以被希尔排序调用
template <class T>
void simple_insertion_sort(vector<T>& Arr, int l, int r, int dist)
{
    for (int i = l; i < r; i += dist) //现在开始移动原来位置为 i 的元素
    {
        for (int j = i; j - dist >= l; j -= dist)
        {
            if (Arr[j - dist] > Arr[j])
                swap(Arr[j - dist], Arr[j]);
            else
                break;
        }
    }
}

//希尔排序
template <class T>
void shell_sort(vector<T>& Arr, int l, int r)
{
    //希尔序列选择 Hibbard 序列 2^i-1
    vector<int> distArr;
    for (int i = log2(Arr.size()); i >= 1; i--)
    {
        distArr.push_back((1 << i) - 1);
    }

    for (int i = 0; i < distArr.size(); i++)
    {
        int dist = distArr[i];
        for (int j = 0; j < dist; j++)
        {
            simple_insertion_sort(Arr, j, r, dist);
        }
    }
}

各种增量序列（了解）

此后，很多数学大牛都来提出了自己的序列。可参考英文维基百科。

希尔伯特（Hibbard）核心：增量序列 $h_k=2^k-1$。其最坏复杂度为 $\Theta(n^\frac{3}{2})$，平均复杂度为 $O(n^\frac{5}{4})$。

目前最新提出的有理论复杂度证明的是 1986 年提出的 Sedwick 序列，他的前几项为 $\{1, 5, 19, 41, 109, …\}$。其递推式在很多国内网站都是错的，正确的如下：

${\begin{cases}
9\left(2^{k}-2^{\frac {k}{2}}\right)+1 & k{\text{is even}} \\
8\cdot 2^{k}-6\cdot 2^{(k+1)/2}+1 & k{\text{is odd}}
\end{cases}}$

按该数列进行希尔排序的最坏复杂度为 $O(n^\frac{3}{4})$，平均复杂度为 $O(n^\frac{7}{6})$。

这么看来希尔排序也不差，$O(n^\frac{7}{6})$ 的复杂度在小数据范围内基本可以和 $O(n \log n)$ 抗衡了（在 $n < 6 \times 10 ^ 8$ 下，$O(n^\frac{7}{6}) < O(n \log_2n)$）。

更新的几个研究成果都是给出了数列和递推式，但是没有给出理论最坏复杂度，大概是没有理论推进的，但是实测表现良好的方法吧。

简单选择排序 Selection Sort

就是扫一遍得到最小的数的下标，与 $a_0$ 交换；再扫一遍得到第二小的数的下标，与 $a_1$ 交换。与冒泡不同的是，他每趟只交换一次数据。

4 2 1 3
1 2 4 3
1 2 4 3
1 2 3 4

简单选择也可以选最大的数的下标。

冒泡排序 Bubble Sort

最形象的算法之一。目的和简单选择一样：每次把没处理的序列的最小者放到最前面（或最大的放到最后面）。但是他的实现是多次交换。

注意，冒泡有两个优化（以下针对“每次把最大的放到最后”的算法）：

1. 算法结束条件改为当前一趟没有交换任何数据。这样，对于有序表，进行 n-1 次比较即可完成排序。
2. 算法需要指定冒泡的最后一个位置 m for(int m = n; m > 0; m--)。但是并不是每个 m 的值都需要执行循环。要是这一趟的交换只交换到了 k(k<n)，下一次可令 m=k-1; 即跳过很多趟无用功。可以看到优化 2 是包含了优化 1 的。

优化后的算法如下：

void BubbleSort(Elem R[]，int n)
{
    m=n;
    while(m>1)
    {
        lastExchangelndex=1;
        for(j=1;j<m;j++)
        {
            if（R[j].key>R[j+1].key)
            {
                Swap（R[j]，R[j+1]);
                lastExchangelndex=j;/*记下进行交换的记录位置*/
            }
        }
        m=lastExchangelndex;/*本趟最后一次交换的位置*/
    }
}

简单选择排序和冒泡排序的每趟结果应该是一样的吧。

快速排序 Quick Sort

快速排序思想就不说了，网上有很多。

空间的支出主要是递归的栈消耗，空间复杂度最好情况是 $O(logn)$ 的，最坏（若原数组基本有序）是 $O(n)$ 的。
时间复杂度最好情况是 $O(nlogn)$ 的，最坏是 $O(n^2)$ 的。

选择枢纽也非常重要，

• 如果选择 a[0] 为枢纽，原数组基本有序，则是 $O(n^2)$ 的复杂度；
• 可以使用 a[rand()] 为枢纽。但是 rand() 比较慢；
• 还可以使用三者取中法：取a[0]、a[n]、a[mid] 的中间值作为枢纽。一般采用这种。

快速排序是不稳定的。

我写的超级丑的代码（完整代码可下载 sort.cpp）：

void quick_sort(vector<int>& Arr, int l, int r)
{
    if (r <= l + 1)
        return;
    int pivot = Arr[l];
    int i = l + 1, j = r - 1;
    while (i < j)
    {
        while (i < j && Arr[i] <= pivot)
            i++;
        while (i < j && Arr[j] >= pivot)
            j--;
        swap(Arr[i], Arr[j]);
    }
    if (Arr[i] <= pivot)
        i++;
    swap(Arr[i - 1ll], Arr[l]); //要让 pivot 即 Arr[l] 与一个小于他的数交换，于是需要判断 Arr[i] 是大于它还是小于它
    quick_sort(Arr, l, i - 1);
    quick_sort(Arr, i, r);
}

如果每次 pivot 取第一个，而数组原本有序，会进行 $O(n^2)$ 次比较和 0 次交换。

枢纽取 l，r，(l+r)/2 位元素的中间大小者，可以优化约 5%。

归并排序 Merge Sort

归并排序是先分解、递归，再进行排序、合并。

归并排序分为 二路归并排序，和多路（k 路）归并排序。

空间主要消耗在新建的数组，复杂度是 $O(n)$ 的。

时间复杂度是 $O(nlogn)$ 的。

归并排序是稳定的。

二路归并的参考代码（完整代码可下载 sort.cpp）：

template <class T>
void merge_sort(vector<T>& Arr, int l, int r)
{
    if (l + 1 >= r)
        return;
    int mid = (l + r) / 2;
    merge_sort(Arr, l, mid);
    merge_sort(Arr, mid, r);

    vector<T> tempArr;
    for (int i = l; i < mid; i++)
    {
        tempArr.push_back(Arr[i]);
    }

    int i = 0, j = mid, cur = l;
    while (i != tempArr.size() && j != r)
    {
        assert(cur < r);
        if (tempArr[i] >= Arr[j])
        {
            Arr[cur] = Arr[j];
            cur++, j++;
        }
        else
        {
            Arr[cur] = tempArr[i];
            cur++, i++;
        }
    }
    while (i != tempArr.size())
    {
        Arr[cur] = tempArr[i];
        cur++, i++;
    }
    assert(cur <= r);
    return;
}

基数排序

基数排序就是多关键字（如 n 进制的第一位、第二位、第三位）排序的一个方法：定好按哪个进行排序，然后就只按照这个关键字排序。

基数排序分为高位优先排序和低位优先排序。

高位优先排序非常直观，先把所有元素按高位排序，然后再把相同高位的元素按次高位排序……以此类推。
但是，高位优先排序的问题是麻烦：第一趟按把所有元素进行排序，第二趟按次高位排序时，需要确定高位相同的每一段的范围。

反而，按低位优先排序会有神奇的特效：

• 第一趟按最低位对所有数进行排序，
• 第二趟按次低位对所有数进行排序，
• …
• 最后一趟按最高位对所有数进行排序。

只要上述的每一趟排序使用的是稳定的排序方法，排完高位以后，相同高位的元素的低位也是有序的。

外部排序

以上学的几种方法都是直接在内存中进行操作的内部排序。

而当数据量太大，无法全部从磁盘读入内存时，就只能把部分数据读入内存，多趟排序，这便是外部排序。

由于 I/O 的速度非常慢，外部排序中，我们主要考虑的是如何减少存储器的读写。
归并排序就很适合外排序，因为他只需要访问被归并序列中的第一个元素。

外部排序的两个阶段：

• 预处理：根据内存大小读取文件记录入内存，用内排序算法排序形成有序片段；
• 归并排序（二路、多路、多阶段）：将有序片段归并为一个有序文件。

下面的例子是以磁带做存储器，因为它的读写过程比较形象。在实际应用中，可以把一个文件看作是一个磁带。

预处理：置换算法

置换算法能在只能容纳 p 个记录的内存内生成平均长度为 2p 的已排序片段。

事实上，只要第一个元素被写入到输出磁带上，他用的内存空间就可以给别的元素使用。当然，这样的前提是，输入磁带的下一个元素比刚输出的元素大。

可以使用优先队列实现这个置换算法+内排序过程。

算法中，如果输入的元素小于等于刚输出的元素，则将其加入优先队列；如果大于刚输出的元素，就可以把它放进优先队列的空余位置（刚空出来的位置）。
反复执行这个过程直至优先队列大小为 0。此时，空余位置也满了，可以对这些数重新构建优先队列。

归并排序：二路归并

1. 把 A1 的数据预处理得到的片段被轮流写到文件 B1 和 B2 上。
2. 然后每次在 B1，B2 磁带上各取一个有序片段，进行二路归并，第一次写到 A1，第二次写到 A2，第三次写到 A1……
3. 下次交换 A1，A2 和 B1，B2 的地位，每次在 A1，A2 磁带上各取一个有序片段，进行二路归并，第一次写到 B1，第二次写到 B2，第三次写到 A3……
4. 重复步骤 2、3 直至只剩一个有序片段，即所有数据经过排序以后的数据。

归并排序：多路归并

多路归并和二路归并的思想基本相同，只有一个细节地方需要处理：

在进行 k 路归并的时候，找到当前 k 路中的最小值，对于二路归并是 $O(1)$ 的复杂度；对于 k 路归并，暴力比较是 $O(k)$ 的复杂度，可以引进优先队列，则每次的复杂度为 $O(\log k)$。

运用多路归并虽然增加了一个树结构，但是复杂度竟然没有变化（二路归并为 $O(n\log_2n)$，k 路归并为 $O(n\log_kn\log_2k)=O(n\log_2n)$），还可以减少磁带读写次数。

归并排序：多阶段归并

多阶段归并是多路归并的优化版本。

显然，k 路归并需要共 2k 条磁带，而多阶段归并可以仅用 k+1 条磁带实现 k 路归并。

过程有点复杂，虽然思想不是很复杂。就是要充分利用空出来的磁带，进行轮流合并。

如果一开始，每条磁带上的有序数列的数量取斐波那契数列时，多阶段归并会有非常好的效果。

（斐波那契数列在最优化中也有应用，真就从小学学到大学啊）

递归与分治

分治的适用情况

抄ppt

1. 该问题的规模缩小到一定的程度就可以容易地解决；
2. 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；
3. 利用该问题分解出的子问题的解可以合并为该问题的解；
4. 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。

能否利用分治法完全取决于问题是否具有第三条特征，如果具备了前两条特征，而不具备第三条特征，则可以考虑贪心算法或动态规划。

而第四特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作：重复地解公共的子问题。此时虽然也可用分治法，但一般用动态规划较好。

分治算法的时间复杂度

戴波的书是参考《算法导论》写的，该节见另一篇博客。

树和二叉树

node 是 结点 不是 节点！！！

于是一口气把之前写的几十个错别字全改了当然是用的查找与替换改的

树中结点的度数是直接儿子的个数，不是图中度数的定义。
数学中就把树二叉树看做从根往叶子结点的有向图，然后讨论的时候点明是出度

二叉树

满二叉树（Full Binary Tree，更加严格）一定是完全二叉树（Complete Binary Tree），反之不一定。搞清定义啊

$n_0=n_2+1$

结点的深度：根结点的深度为 1，往下依次加大。可从字面理解“深度”。
树的深度：即是根结点的深度。

存储结构分为：

• 顺序
• 链式：又分为二叉链式、三叉链式（指加了一个父结点的指针）

遍历方法：

• 递归遍历（递归）
  • 先中后序遍历中的先、中、后指的是根结点的访问的次序，左右结点都是先左后右。
  • 先中/后中可以还原子树，貌似给任意两种遍历方式都能指出父子关系。
• 层次遍历（队列）
• 非递归遍历

层次遍历的示例代码：

queue<Node*> q;
q.push(root);
while(!q.empty())
{
    int sz = q.size();             // 一层一层地遍历，避免分不清层次
    for (int i = 0; i < sz; i++)
    {
        Node* cur = q.front();
        q.pop();
        if (cur->left)
            q.push(cur->left);
        if (cur->right)
            q.push(cur->right);
    }
}

二叉排序树

左<父<右 的二叉树，又叫二叉搜索树 Binary Search Tree。树中不存在相同的元素。

查找、插入都无脑。

删除的时候讨论一下就行，画画图的事情。注意对于待删除结点左右子树结点都存在的情况，有两种做法，分别是让其左子树顶上去和让其右子树顶上去，都可以。

注意二叉排序树复杂度也可能爆炸，原因是没有控制树高为 $\log n$。下面几种算法就会通过不同的限制，来控制树高。

平衡二叉树（AVL Tree）

平衡二叉树是一种二叉排序树，但是其左右结点数会较为平衡，使得树高能控制在 $\log n$。

课程这里提到的实际上是平衡二叉树的一种——AVL 树。平衡二叉树的实现方法还有红黑树、伸展树、B树（B树不是二叉树，但是树高能控制在 $\log n$）等。

AVL 控制树高的方法是强制要求 每个结点的左右子树高度差不超过 1。

在插入、删除的时候涉及到了左旋、右旋等。多处需要旋转的时候，是从靠向叶子的地方开始旋转进行平衡。

旋转具体分为 LL（单向左旋）、RR（单向右旋）、LR（先左后右）、RL（先右后左）。下面直接贴 ppt 了。

单向左旋

单向右旋

先左后右

先右后左

还是有一点迷。

Huffman 树 和 Huffman 编码

维基百科对 Huffman 编码的定义：

在计算机数据处理中，霍夫曼编码使用变长编码表对源符号（如文件中的一个字母）进行编码，其中变长编码表是通过一种评估来源符号出现几率的方法得到的，出现几率高的字母使用较短的编码，反之出现几率低的则使用较长的编码，这便使编码之后的字符串的平均长度、期望值降低，从而达到无损压缩数据的目的。

例如，在英文中，e的出现几率最高，而z的出现概率则最低。当利用霍夫曼编码对一篇英文进行压缩时，e极有可能用一个比特来表示，而z则可能花去25个比特（不是26）。用普通的表示方法时，每个英文字母均占用一个字节，即8个比特。二者相比，e使用了一般编码的1/8的长度，z则使用了3倍多。倘若我们能实现对于英文中各个字母出现概率的较准确的估算，就可以大幅度提高无损压缩的比例。

Huffman 编码的（一种）计算方法是构造 Huffman 树。

维基百科对 Huffman 树的定义：

霍夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的路径长度是从树根到每一结点的路径长度之和，记为WPL=（W1L1+W2L2+W3L3+…+WnLn），N个权值Wi（i=1,2,…n）构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li（i=1,2,…n）。可以证明霍夫曼树的WPL是最小的。

由定义可以看出，把所有需要编码的源符号作为二叉树的结点，如果构造出的二叉树 WPL 越小，压缩比例就越高。

如何将 Huffman 树转化为 Huffman 编码呢？将 Huffman 树的每个结点的左右孩子命名为 0 和 1（也可以交换），某符号的编码就是从根结点往下遍历到该符号代表的叶子结点过程中，经过的所有结点组成的 01 字符串。

上面是将 Huffman 树转化为编码，那如何通过给定概率（给定权重）构造出 Huffman 树呢？

简单的来说，就是每一步：

1. 构造一个新的结点；
2. 每次优先将权值最小的两个结点，通过作为新构造的结点的左右孩子，合并为一棵二叉树；
3. 新结点的权值为两个结点的权值之和；
4. 将刚才讨论的两个结点从集合中删除，然后将新结点加入。

如此反复，直至 n 个字符代表的 n 个叶子结点变为一个结点。

构造的过程容易懂。实现需要堆。证明需要贪心。

Huffman 可以应用于压缩文件，压缩率在 20%~90% 之间。

Huffman 编码贪心选择性质分析

这部分参考了《算法导论（第三版）》。

符号	说明
$f_x$	$x$ 出现的频度
$d_T(x)$	$x$ 在 $T$ 树的深度
$WPL(T)$	$T$ 树的 WPL（带权路径长度）
	$WPL(T)=\sum_{x \in T} f_x \cdot d_T(x)$

我们即要证明，一个序列 $S$ 的 Huffman 树是具有最小 WPL（带权路径长度）的二叉树。

我们的证明思路是：

证明引理 1（贪心选择）：对于一个序列，$y$ 和 $z$ 是其最小频度的字母。由这个序列中组成的 WPL 最小的二叉树中，一定存在一棵树，其中 $y$ 和 $z$ 是具有最大深度的兄弟子结点。
证明引理 2（最优子结构）：对于一棵二叉树 $T$，设 $y$、$z$ 为其两个叶子且互为兄弟，他们的父亲是 $\omega$。若将 $\omega$ 看做具有权重（频率）$f_\omega = f_y + f_z$ 的叶子结点，按此法得到的树 $T’$ 具有最小 WPL，则 $T$ 也具有最优子结构。

首先证明引理 1：对于一个序列，$y$ 和 $z$ 是其最小频度的字母。由这个序列中组成的 WPL 最小的二叉树中，一定存在一棵树，其中 $y$ 和 $z$ 是具有最大深度的兄弟子结点。

我们使用交换论证：设 $T$ 为 WPL 最小的二叉树，其最大深度兄弟子结点为 $a$, $b$。不失一般性地假设 $f_y \leq f_z$，$f_a \leq f_b$。由于 $y$、$z$ 频度最小，显然有 $f_y \leq f_a$，$f_z \leq f_b$。在此前提下，设将 $T$ 的 $a$、$y$ 结点交换得到的树为 $T’$，将 $T’$ 的 $b$、$z$ 结点交换得到的树为 $T’’$。

树 $T$ 和 $T’$ 的 WPL 之差为：

$$\begin{aligned}
WPL(T)-WPL(T’) &= \sum_{x \in T} f_x \cdot d_T(x) - \sum_{x \in T’} f_x \cdot d_T’(x) \\
&= f_a \cdot d_T(a) + f_y \cdot d_T(y) - f_a \cdot d_{T’}(a) - f_y \cdot d_{T’}(y) \\
&= f_a \cdot d_T(a) + f_y \cdot d_T(y) - f_a \cdot d_T(y) - f_y \cdot d_T(a) \qquad \left( d_{T’}(a)=d_T(y) \right) \\
&= (f_a - f_y) \cdot (d_T(a) - d_T(y)) \geq 0 \qquad \left(两项都非负\right)
\end{aligned}$$

所以 $WPL(T) \geq WPL(T’)$。同理 $WPL(T’) \geq WPL(T’’)$。又因为 $T$ 为最下 WPL，故有 $WPL(T) \leq WPL(T’’)$。
由三个不等式可得，$WPL(T) = WPL(T’’)$，即 $T’’$ 的 WPL 也是最小。引理 1 得证。

在证明引理 2 之前，我们先证明引理 3：对于一棵二叉树 $T$，设 $y$、$z$ 为其两个叶子且互为兄弟，他们的父亲是 $\omega$。若将 $\omega$ 看做具有权重（频率）$f_\omega = f_y + f_z$ 的叶子结点，按此法得到了树 $T’$，则有：

$$WPL(T’)=WPL(T)-f_y-f_z$$

证明如下：

$$\begin{aligned}
WPL(T) &= \sum_{x \in T} f_x \cdot d_T(x) \\
&= f_y \cdot d_T(y) + f_z \cdot d_T(z) + \sum_{x \in T, x \neq y, x \neq z} f_x \cdot d_T(x) \\
&= (f_y + f_z) \cdot (1 + d_{T’}(\omega)) + \sum_{x \in T, x \neq y, x \neq z} f_x \cdot d_T(x) \\
&= f_y + f_z + \left[ f_{T’}(\omega) \cdot d_{T’}(\omega) + \sum_{x \in T’, x \neq \omega} f_x \cdot d_{T’}(x) \right] \\
&= f_y + f_z + WPL(T’)
\end{aligned}$$

有了这个性质，这样贪心的思路基本就清楚了。剩下的就是按照贪心的套路证明。数学归纳法 + 反证法：

证明引理 2：如果按上面方法构造的 $T’$ 是序列 $S’=S - \{y, z\} + \{\omega\}$ 的最优树，则 $T$ 是序列 $S$ 的最优树。

令 $n = |S|$。

• 当 $n = 2$ 时，显然一个根结点和两个叶子结点的结构具有最小 WPL；
• 当 $n \geq 2$ 时，假设存在大小为 $n$ 的更优编码的树 $Z$，其最深的兄弟子结点为 $a$ 和 $b$。
  • 按引理 1 的方式将 $Z$ 树中 $a$、$b$ 和 $y$、$z$ 互换，得到 $Z’$。由引理 1 有 $WPL(Z) = WPL(Z’)$；
  • 按引理 3 的方式将 $Z’$ 树中 $y$、$z$ 替换为 $\omega$，得到 $Z’’$。由引理 3 有 $WPL(Z’’) = WPL(Z’) - f_y - f_z$；
  • 此时的 $Z’’$ 为 $T’$ 树的另一个排序方式，由于 $T’$ 的 WPL 最优，有 $WPL(T’) \leq WPL(Z’’)$。
  • 由引理 3 有：$WPL(T’)=WPL(T)-f_y-f_z$
  • 综上有：$WPL(Z) = WPL(Z’) = WPL(Z’’) + f_y + f_z \geq WPL(T’) + f_y + f_z = WPL(T)$，即 $WPL(Z) \geq WPL(T)$，证毕。

有了引理 2，由数学归纳法可得：一个序列 $S$ 的 Huffman 树是具有最小 WPL（带权路径长度）的二叉树。证明完毕。

堆 Heap

这部分参考了《算法导论（第三版）》。

就是 C++ 的 priority_queue 的实现过程啦。

堆是完全二叉树，同时（小根堆/小顶堆）要求根结点小于两个结点，大根堆同理。（因此堆不是二叉排序树）

完全二叉树，一可以保证 $\lfloor \log n \rfloor$ 的树高，二可以用线性表实现。

以上是堆的性质，下面一步一步的说（大根）堆的实现和应用：

• max_heapify(Array, index)，作用是在以 index 的左右儿子为根的完全二叉树符合堆性质的前提下，通过调整使得以 index 为根的二叉树符合堆性质，时间复杂度 $O(\log n)$；
• build_max_heap(Array)，将任意数组调整为堆，时间复杂度 $O(n)$；
• heap_sort(Array)，将任意数组使用堆结构进行排序，时间复杂度 $O(n \log n)$；
• heap_insert(value)、heap_pop_max()、heap_max()，将堆作为优先队列使用，每一步的时间复杂度都是 $O(\log n)$。

完整的代码因为较长，不在这里贴出，可下载 sort.cpp。

max_heapify

max_heapify(Array, index)，作用是在以 index 的左右儿子为根的完全二叉树符合堆性质的前提下，通过调整使得以 index 为根的二叉树符合堆性质，时间复杂度 $O(\log n)$。

实现上，就是只考虑 index 为根的二叉树，将小的根一直向下沉，将左右结点中较小的一个往上冒，然后再处理这边的子树。

这里的 $O(\log n)$ 的时间复杂度是指，操作的复杂度与以该结点为根结点的子树的深度成正比（也就是说，叶子结点的复杂度最小，根结点最大）。至于如何由这句话严格地推出 $O(\log n)$，这里不加赘述。

参考代码：

template <class T>
void max_heapify(vector<T>& Arr, int i, int size) //size 参数是堆的大小，在堆排序过程中，堆的大小不一直等于数组的大小
{
    while (i < size)
    {
        int l = leftson(i), r = rightson(i), largest;
        if (l < size && Arr[i] < Arr[l])
            largest = l;
        else
            largest = i;
        if (r < size && Arr[largest] < Arr[r])
            largest = r;

        if (largest == i)
            break;
        else
        {
            swap(Arr[i], Arr[largest]);
            i = largest;
        }
    }
}

build_max_heap

堆的实现中，不是像 priority_queue 一样，一个一个加进来，而是将一个数组逐步调整为堆。
调整的具体方法，是从最后一个非叶子结点往根结点方向调整，使得调整的结点以下部分都满足堆的性质。

代码非常简洁，就是 max_heapify 外面套一个 for。

template <class T>
void build_max_heap(vector<T>& Arr)
{
    for (int i = Arr.size() - 1; i >= 0; i--)
    {
        max_heapify(Arr, i, Arr.size());
    }
}

但是正确性的证明需要用到循环不变式，这也是《算法导论》一直在强调的东西。此处略去详细的证明。

时间复杂度的一个上界 $O(n \log n)$ 是显然的。

但是实际上它是 $O(n)$ 的！

证明如下：

为简洁起见，我们设树高为 $h$。显然有 $h = O(\log n)$。

由 max_heapify 的复杂度分析，我们可以知道，该函数的复杂度是和以结点为根结点的树的深度成正比的。即根结点的复杂度为 $O(h)$，叶子结点为 $O(1)$。build_max_heap 对所有结点进行了 max_heapify，所以时间复杂度为：

$$O(\sum_{i=1}^h (h+1-i)\cdot 2^i) = O(4 \cdot 2^h - 2h - 4) = O(2^h) = O(n)$$

其中可能需要用到等比数列求和或级数求和的技巧。

heap_sort

用堆实现排序的方法是，

1. 首先 build_max_heap 将数组调整成（大根）堆，此时最大的数一定在堆顶。
2. 将其取出（实际上是和堆的最后一个元素交换，然后堆的大小 –），再重新 max_heapify 调整为堆。如此反复，直至堆大小为 0，此时原数组正好就是升序排列的。

（值得一提的是，实现升序排序，推荐的反而是大根堆，因为取走堆顶元素以后丢到线性表末尾，堆的大小为 0 时，得到的序列就是升序的）

因此 pop 过程不需要重新写删除元素的函数（所以也就只能删除堆顶的元素了好歹人家也是完全二叉树，删了中间的结点就不是完全二叉树了）。

所以，堆排序实际分为两个步骤：先将数组调整为堆 build_max_heap，时间复杂度 $O(n)$，再反复 pop 堆顶元素再调整，时间复杂度 $O(n\log n)$，总时间复杂度也为 $O(n\log n)$。

代码如下：

template <class T>
void heap_sort(vector<T>& Arr, int l, int r)//非递归排序，不需要 l, r 参数，但为了统一，还是设定了这个参数
{
    using namespace heap;
    //先将数组调整为堆
    build_max_heap(Arr);

    for (int i = Arr.size() - 1; i > 0; i--)
    {
        swap(Arr[i], Arr[0]);
        max_heapify(Arr, 0, i);
    }
}

这里是对根结点进行了 $n$ 次 max_heapify，所以时间复杂度是 $O(n\log n)$。

heap_insert

这里的 heap_insert 和《算法导论》上的实现思想略微有点不同，但是算法复杂度数量级是相同的。

这里的思想是在最后插入一个结点（使用 C++ 的 std::vector 的 push_back 函数），然后对新结点往上的结点都使用一次 max_heapify。

注意到在原来已经是一个堆的前提下，这样的每次 max_heapify 都只会进行一次循环就结束，其实是 $O(1)$ 的，因此可以也保证时间复杂度是 $O(\log n)$。

具体实现上，对于优先队列我创建了类 priority_queue。函数名为了与 std::priority_queue 保持一致，这里的 heap_insert 用的是 push。

template <class T>
class priority_queue //为突出算法核心并保持代码简洁，不进行异常情的检查
{
private:
    vector<T> Arr;
public:
    void push(const T val)
	{
        Arr.push_back(val);
        for (int i = Arr.size() - 1; i >= 0; i = father(i))
        {
            max_heapify(Arr, i, Arr.size());
        }
    }
}

heap_heap_pop_max

pop 过程和 heap_sort 的 10、11 行内容接近。就是将根结点和最后一个结点进行交换（方便 vector::pop_back 去掉最后一个元素），然后 max_heapify。

void pop()
{
    swap(Arr[0], Arr[Arr.size() - 1]);
    Arr.pop_back();
    max_heapify(Arr, 0, Arr.size());
}

heap_max

一行，返回根结点就行。

T top()
{
    return Arr[0];
}

完整的结构体代码和其他堆的代码都可以参见 sort.cpp。

树

森林就是一堆树。将森林的每棵树的根结点加上一个父结点以后，又变成了一棵树。

存储结构

• 双亲表示法：每个结点只存值和父结点。
• 孩子表示法：每个结点的一堆儿子结点指针拉成链表来存。
• 兄弟表示法：每个结点存儿子结点和右边的兄弟结点。这个挺有意思的，可以直接由二叉树的结构改过来。

兄弟表示法与二叉树的转换（指的是同一个存储结构用二叉树和兄弟表示法两种形式解释的结果）：
森林结点的儿子存储在二叉树的左结点，森林结点的兄弟存在二叉树的右结点。二叉树根结点的右结点一定为空。

最后这个特性很有意思，就可以把森林的每个根结点用根结点的右节点串起来，即实现了森林和二叉树的转换。

遍历方法

非二叉树没有中序遍历废话

森林有先序、中序，没有后序。后序没有意义（先把别人的树访问完了再来访问自己的根结点？？？）

引用：计算表达式

• 后缀表达式天下第一
• 中缀表达式不唯一
• 前缀表达式的实现需要两个栈

图论和贪心算法

贪心算法

贪心算法就是每一步寻求局部最优解。证明全局最优，可以通过修改最优解得到贪心解，然后将问题划归为最优子结构，最后用数学归纳法证明。

另外的证明方式可以看算法设计

最小生成树

1. 朴素 Prim 在稠密图中优于 Kruskal，在稀疏图中劣于 Kruskal。
2. 堆优化 Prim 在任何时候的时间复杂度都优于朴素 Prim 和 Kruskal，代价是空间消耗极大。

后记

由于课程紧张，后期笔记就比较水了。

这是中国大学 MOOC 的学习链接。

2019.12.29 更新：明天考数据结构，今天看了下笔记，发现做笔记还是很香的，虽然前期很花时间，但是复习起来不要太舒服，特别是排序章节。