本讲将会在二叉树结构的基础上在介绍另外三种特殊的结构：堆、哈夫曼树和集合，快来学习吧！
Heap
在了解对之前先来考虑一下“优先队列”的问题。
所谓优先队列，即取出元素的顺序是依照元素的优先权（关键字）大小，而不是元素进入队列的先后顺序，可以用数组、链表、有序数组、有序链表、树等来实现。
如果使用平衡二叉树来实现，插入不难实现，但是删除操作会存在一个问题，那就是，多次删除操作后，树的两边会变得不均衡，如果在来旋转调整就会降低效率，于是考虑让最大值成为根结点（大根堆），每次删除只需要删除根结点即可，这样就不会影响树的高度了。
堆有两个特性（满足特性才能称堆，否则不行）：
- 结构性：用数组表示的完全二叉树
- 有序性：任一结点的关键字是其子树所有结点的最大值（或最小值）。
- 最大堆（MaxHeap），也称大根堆，根为最大值
- 最小堆（MinHeap），也称小根堆，根为最小值
堆的抽象数据类型描述
类型名称：最大堆（MaxHeap）
数据对象集：完全二叉树，每个结点元素值不小于其子结点的元素值
操作集：最大堆$H ∈ MaxHeap$，元素$item ∈ ElementType$，主要操作有：
- MaxHeap Create(int MaxSize)，创建一个空的最大堆
- Boolean IsFull(MaxHeap H)，判断最大堆H是否已满
- Insert(MaxHeap H, ElementType item)，将元素item插入最大堆H
- Boolean IsEmpty(MaxHeap H)，判断最大堆H是否为空
- ElementType DeleteMax(MaxHeap H)，返回H中最大元素（高优先级）
堆的实现
C 语言下的堆定义可以如下：1
2
3
4
5
6typedef struct HeapStruct *MaxHeap;
struct HeapStruct{
ElementType *Data;
int Size;
int Capacity;
};
最大堆
初始化（建立空堆）
1 | MaxHeap Createheap(int MaxSize) { |
判断堆满
1 | bool Isfull(MaxHeap H) { |
判断堆空
1 | bool Isempty(MaxHeap H) { |
插入
由于堆的实现是基于完全二叉树的思想，插入元素的时候直接放在最后就好。但是要注意为了保证树的结构符合最大堆的特性，所以需要将子结点与父结点比较，如果子结点比父结点大，就将子结点与父结点互换。1
2
3
4
5
6
7
8
9
10
11
12
13
14bool Insert(MaxHeap H, ElementType X) {
int i;
if(Isfull(H)) {
printf("The heap is full!\n");
return false;
} else {
i = ++H->Size;
for(; H->Data[i / 2] < X; i /= 2) {
H->Data[i] = H->Data[i / 2];
}
H->Data[i] = X;
return true;
}
}
删除
对大根堆而言，删除就是删除最大值元素（也就是堆顶）。删除了堆顶后，直接将最后一个元素放到堆顶显然无法保证堆的结构性，所以还需要对此时的堆做调整。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18ElementType DeleteMax(MaxHeap H) {
int parent, child;
ElementType Maxitem, X;
if(Isempty(H)) {
printf("The heap is empty!\n");
return ERROR;
}
Maxitem = H->Data[1];
X = H->Data[H->Size--];
for(parent = 1; parent * 2 <= H->Size; parent = child) {
child = parent * 2;
if((child != H->Size) && (H->Data[child] < H->Data[child + 1])) child++;
if(X >= H->Data[child]) break;
else H->Data[parent] = H->Data[child];
}
H->Data[parent] = X;
return Maxitem;
}
直接建堆
上面提到的建堆方法实际上是将元素一个个的插入到堆中，时间复杂度为：$O(NLogN)$。
可以使用下面的思路来建堆：
- 将 N 个元素按输入顺序存入，先满足完全二叉树的特性
- 调整各结点位置，以满足最大堆的有序特性。
叶子结点无须调整，所以只需依次调整所有非叶结点即可，调整的思路与删除结点时调整堆的结构的思路一致。另外，为了使得代码简洁，可以将结点下移的操作独立封装出来，代码如下：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18void Percdown(MaxHeap H, int p) {
int parent, child;
ElementType X;
X = H->Data[p];
for(parent = p; parent * 2 <= H->Size; parent = child) {
child = parent * 2;
if((child != H->Size) && (H->Data[child] < H->Data[child + 1])) child++;
if(X >= H->Data[child]) break;
else H->Data[parent] = H->Data[child];
}
H->Data[parent] = X;
}
void Buildheap(MaxHeap H) {
int i;
for(i = H->Size / 2; i > 0; i--) {
Percdown(H, i);
}
}
尽管从代码上看时间复杂度好像是$O(N^2)$，但实际情况的时间复杂度是$O(NLogN)$。
测试代码
1 |
|
最小堆
最小堆的结构与最大堆的结构区别只在于根结点值比叶结点都小，本质上还是一棵完全二叉树。所以，最小堆的插入、删除和直接建堆的代码略有差异，但思路都是一致的。
插入
前面介绍最大堆的时候已经知道了，每向堆中插入一个结点就需要调整堆的结构，调整这个操作可以独立封装起来，这样可以使得代码更加简洁。整体代码如下：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18void Percup(MinHeap H, int index) {
int tmp = H->Data[index];
for(; H->Data[index / 2] > H->Data[index] && index > 1; index /= 2) {
H->Data[index] = H->Data[index / 2];
}
H->Data[index] = tmp;
}
bool Insert(MinHeap H, int X) {
if(Isfull(H)) {
printf("The heap is full!\n");
return false;
} else {
H->Data[++H->Size] = X;
Percup(H, H->Size);
return true;
}
return true;
}
删除
注意最小堆中删除操作的 Percdown 函数与最大堆是有区别的，主要在于当叶结点小于根节点时，才需要将根结点下移（而此时最大堆刚好就是合适的位置）。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22void Percdown(MinHeap H, int index) {
int tmp = H->Data[index];
int parent, child;
for(parent = index; parent * 2 <= H->Size; parent = child) {
child = parent * 2;
if((child != H->Size) && (H->Data[child] > H->Data[child + 1])) child++;
if(tmp > H->Data[child]) H->Data[parent] = H->Data[child];
else break;
}
H->Data[parent] = tmp;
}
int Deletemin(MinHeap H) {
int Minitem;
if(Isempty(H)) {
printf("The heap is empty!\n");
return false;
}
Minitem = H->Data[1];
H->Data[1] = H->Data[H->Size--];
Percdown(H, 1);
return Minitem;
}
直接建堆
直接建堆的思路一致，不同的只是最小堆的 Percdown 函数与最大堆不同，但是可以发现 Buildheap 这个函数没有变化，这其实就是将 Percdown 独立封装起来的好处。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17void Percdown(MinHeap H, int index) {
int tmp = H->Data[index];
int parent, child;
for(parent = index; parent * 2 <= H->Size; parent = child) {
child = parent * 2;
if((child != H->Size) && (H->Data[child] > H->Data[child + 1])) child++;
if(tmp > H->Data[child]) H->Data[parent] = H->Data[child];
else break;
}
H->Data[parent] = tmp;
}
void Buildheap(MaxHeap H) {
int i;
for(i = H->Size / 2; i > 0; i--) {
Percdown(H, i);
}
}
测试代码
1 |
|
Huffman Tree
编码问题是计算机学科内十分重要的问题，而哈夫曼树就是为了解决编码的问题而产生的。与之类似的问题还有判定树和搜索树如何构造最优的问题，而所谓最优，即是查找树效率最高。
首先，哈夫曼树是一种很特殊的二叉树（没错，它是二叉树），它有 N 个叶子结点，若
该树的带权路径长度（WPL）达到最小，称这样的二叉树为哈夫曼树（Huffman Tree），也叫最优二叉树。
那么，什么是带权路径长度（WPL，Weighted Path Length of Tree）呢？
设二叉树有 N 个叶子结点，每个叶子结点带有权值$w_k$，从根结点到每个叶子结点的长度为$l_k$，则每个叶子结点的带权路径长度之和：$WPL = \sum_{k=1}^n w_k l_k$。也就是说，哈夫曼树实际上就是指 WPL 最小的树。
构造
构造哈夫曼树的方法也比较简单，每次把权值最小的两棵二叉树合并即可。
由于每次建树都需要选出权值最小的结点，所以在代码实现过程中，借助最小堆来找出权值最小的结点比较方便快捷。
这里偷个懒，直接用何头给出的代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19typedef struct TreeNode *HuffmanTree;
struct TreeNode{
int Weight;
HuffmanTree Left, Right;
}
HuffmanTree Huffman(MinHeap H) {
int i;
HuffmanTree T;
BuildMinHeap(H);
for(i = 1; i < H->Size; i++) {
T = malloc(sizeof(struct TreeNode));
T->Left = Deletemin(H);
T->Right = Deletemin(H);
T->Weight = T->Left->Weight + T->Right->Weight;
Insert(H, T);
}
T = DeleteMin(H); // insert new root node
return T;
}
特点
由于哈夫曼树构造方法的特殊性，它具有以下几个特点：
- 没有度为 1 的结点
- n 个叶子结点的哈夫曼树共有 $2n-1$ 个结点
- 哈夫曼树的任意非叶结点的左右子树交换后仍是哈夫曼树
- 对同一组权值${w_1, w_2, w_3, \dots, w_n}$，是存在不同构的两棵哈夫曼树，但注意其 WPL 是一定是一样且最小的
记好这些特点，算法笔试题可能会遇见。
编码
如前所言，哈夫曼树的出现是为了解决编码问题，那么具体解决了那些问题呢？
哈夫曼树解决的编码问题就是避免了在进行不等长编码时的可能会产生的二义性。所谓二义性就是指同一串编码，解释结果会有不同。根据哈夫曼树的结构，如果用字符代表叶结点，左右分支分别代表 0 和 1，用根结点到每个叶结点的路径方向代表每个字符的编码，可以很神器的发现，各种字符编码组合都不会产生二义性。
此时，对每个字符所编的码也叫做前缀码（即任何字符的编码都不是另一字符编码的前缀）。实际上而言，当所有字符都处在叶结点时，就不会产生非前缀码。
按照哈夫曼树进行的编码，还有一个优点，那就是代价最小，比起等长编码要节省了大量的空间。
这就是哈夫曼树所解决的编码问题。
Set
这里集合的概念与数学上集合的概念基本一致，但实际经常用到的集合叫做“并查集”，其实就是集合的并和查两个操作。
PS：学完整套课程之后，回过头会发现，集合更像是后面要学的“图”，但其中一些概念又与树联系密切。
利用静态数组存储集合较为方便，借用一下何头的代码：1
2
3
4typedef struct {
ElementType Data;
int Parent;
} SetType;
查找
查找某个元素所在的集合，要先找到这个结点的位置，然后在从下往上依次查找根结点，代码如下：1
2
3
4
5
6
7int Find(SetType S[], ElementType X) {
int i;
for(i = 0; i < MaxSize && S[i].Data != X; i++)
if(i >= MaxSize) return -1; // not find the element
for(; S[i].Parent >= 0; i = S[i].Parent);
return i; // return the root static pointer
}
并
两个集合的并运算需要在查找操作的基础上实现，先分别找到两个集合的根结点，再将其中一个根结点的父结点指针设置成另一个根结点的数组下标，假设两个集合内分别有元素 $X_1$ 和 $X_2$，代码如下：1
2
3
4
5
6void Union(SetType S[], ElementType X1, ElementType X2) {
int Root1, Root2;
Root1 = Find(S, X1);
Root2 = Find(S, X2);
if(Root1 != Root2) S[Root2].Parent = Root1;
}
按照上面的思路，当不断的并入新集合时，可能会产生树不断增高的情况，这样会导致查找的效率降低，一种可行的办法就是将小集合并入大集合。但这样做的效率仍然不高，不过后面姥姥会交给我们路径压缩和按秩归并的方法。
Homework
05-7 堆中的路径
题目意思很明确，利用题目给定的一串数字建立最小堆，然后对任意给定的下标 i，打印 H[i] 到根结点的路径即可。
1 |
|
05-8 File Transfer
这道题与老师上课讲的连网问题很类似，但是要看清楚题目中I C S分别代表的含义。
I代表输入连接，就相当于将两个元素并成一个集合；C代表检查两个元素是否在一个集合；S代表停止测试。
根据题目的测试样例，我们得现构造集合，然后在判断元素是否在同一个集合内。当然了，一开始所有的元素都是一个独立的集合，只有当“输入连接”后两个元素才算是处于同一个集合。
明白以上原则后，按照题目要求来进行输出即可。
另外，姥姥出这道题的目的就是为了给大家介绍路径压缩与按秩归并，不用这两种方法，显然不能 AC。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
typedef int Set[MAXN];
typedef int SetType;
void init(Set S) {
int i;
for(i = 0; i < MAXN; i++) {
S[i] = -1;
}
}
void Union(Set S, int root1, int root2) {
if(S[root1] < S[root2]) {
S[root1] += S[root2];
S[root2] = root1;
} else {
S[root2] += S[root1];
S[root1] = root2;
}
}
SetType Find(Set S, int elem) {
if(S[elem] < 0) return elem;
else return S[elem] = Find(S, S[elem]);
}
int main() {
Set set;
init(set);
int i, n, c1, c2;
scanf("%d%*c", &n);
char act;
while((act = getchar()) != 'S') {
scanf("%d %d%*c", &c1, &c2);
int root1, root2;
root1 = Find(set, c1);
root2 = Find(set, c2);
if(act == 'C') {
if(root1 == root2 && (root1 > 0 || root2 > 0)) printf("yes\n");
else printf("no\n");
} else if(act == 'I') {
Union(set, root1, root2);
}
}
int cnt = 0;
for(i = 1; i <= n; i++) {
if(set[i] < 0) cnt++;
}
if(cnt == 1) printf("The network is connected.\n");
else printf("There are %d components.\n", cnt);
return 0;
}
按秩归并
姥姥讲解的按秩归并有两种方法，关键取决于如何理解“秩”，可以将其认为是树高，也可以认为是树结点的个数。但两者有一个共同点，那就是将小规模的树并到大规模的树上。1
2
3
4
5
6
7
8
9void Union(Set S, int root1, int root2) {
if(S[root1] < S[root2]) {
S[root1] += S[root2];
S[root2] = root1;
} else {
S[root2] += S[root1];
S[root1] = root2;
}
}
路径压缩
路径压缩所解决的问题是尽可能的降低树的高度，这样就会使得其查找效率提高。
在之前介绍的查找操作中，每次需要先找到叶结点在去找根结点，找到了之后并不对集合（也就是查找树）的结构做出优化。但路径压缩借助递归，每找到一个结点，就将它直接挂在根结点的下面，这样当找到目标结点的根结点时，这棵查找树的高度就是 2 了，极大的提高了下次查找时的效率。1
2
3
4SetType Find(Set S, int elem) {
if(S[elem] < 0) return elem;
else return S[elem] = Find(S, S[elem]);
}
05-9 Huffman Codes
题目大意就是给定字符出现的频率，判断给定的测试样例是否是最优解，但要注意最优解可能并不是由哈夫曼树构成的。
当初做这个题时，想方设法的偷懒，非常不情愿建哈夫曼树，结果最后还真找到了 AC 的方法。
虽然不建哈夫曼树，但是 WPL 还是需要计算出来用来判定是否最优的。那么如何计算 WPL 呢？对，继续偷懒，直接用 C++ STL 里面的优先队列（其实就是最小堆），核心思路就是哈夫曼树的 WPL 也等于除了根结点以外，全部结点的权值之和。这种计算方法与老师上课讲的是完全不同了，利用这种思路，可以很简单的计算出一棵哈夫曼树的 WPL，而且还不用建树。
有了最优解的 WPL 后，只需要在计算出每个样例的 WPL，并比对是否一致即可知道样例是否正确。
明白以上问题后，基本已经解决这道题目了。不过还有一个地方要注意，对于非前缀码且 WPL 相同的样例，就不是正确结果了。所以，在计算样例的 WPL 后，还需要判断样例中是否有非前缀码的存在，如果有，那就不是正确结果，需判定为 No。
1 |
|
