堆与哈夫曼树

2020-03-07

数据结构与算法

字数统计: 2.8k字 | 阅读时长≈ 10分钟

堆与哈夫曼树的总结

堆与哈夫曼树

堆

前置知识(5min)

什么是二叉树

二叉树是每个结点最多有两个子树的树结构

什么是满二叉树

一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树

什么是完全二叉树

对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树

用一张图可以较清楚的展示三者的区别

tm3eG8udaivQlF4.png (1294×599)

堆是什么(0.5min)

堆是计算机科学中的一类数据结构

堆有什么特点(5min)

堆总是一颗完全二叉树
堆中任意一个节点总是不大于（或不小于）其父节点的值

[换言之，任意一个父节点的值一定大于等于（或小于等于）其所有子节点的值]

例如：

上述完全二叉树中，任意一个节点的值一定大于其子节点的值

7 > 4 且 7 > 6

4 > 1 且 4 > 3

6 > 2 且 6 > 5

因此，这课完全二叉树就可以叫做堆

补充：

任意父节点大于等于子节点的堆叫大顶堆
任意父节点小于等于子节点的堆叫小顶堆

堆有什么用(4.5min)

基于堆的特点，我们发现堆可以：

快速获取一些元素中最大的值（或最小的值）（通过查询根节点的值实现）
通过不断取出当前元素中最大（或最小）的值来实现排序

例如：

现在有一个堆，堆中的元素有[6, 8, 4]，规定这是一个大顶堆。

首先我们取出根节点，也就是 8，把 8 放入序列

然后继续取出根节点，这时根节点是 6，把 6 放入序列

然后继续取出根节点，这时根节点是 4，把 4 放入序列

排序完成，新序列为[8, 6, 4]。

如何建立一个堆(15min)

完全二叉树的一个性质(7min)

上图是一颗完全二叉树，红字部分为给每个节点的标号，不难发现这样一个特点：

对于任意一个节点，其左儿子标号=该节点标号*2，其右儿子标号=该节点标号 *2+1

上图中：

2 = 1 * 2， 3 = 1 * 2 + 1

4 = 2 * 2， 5 = 2 * 2 + 1

6 = 3 * 2， 7 = 3 * 2 + 1

用数组表示树(7.5min)

基于上面得到的性质，可以用一段数组来表示一颗完全二叉树，而不再使用树形结构。

只需按照标号顺序依次向数组中放入每个节点即可用数组表示完全二叉树

例如在发现完全二叉树性质时使用的例子：

其数组表示为：

[7, 4, 6, 1, 3, 2, 5]

其标号顺序为：

[1, 2, 3, ,4, 5, 6, 7]

用数组建立一个空堆(0.5min)

那么如果要建立一个空堆（即没有任何元素的堆），只需要声明一个数组即可，因为堆本质就是一颗特殊的完全二叉树。

之后的讨论中默认新建的这个堆为大顶堆

1	int heap[N];

向堆中插入一个元素(15min)

在尾部添加新元素(3min)

现在向堆中插入第一个元素，我们只需要在数组的尾部插入即可，例如我们插入 4

现在数组变为[4]，表现为树形结构为：

然后，插入第二个元素 6

现在数组变为[4, 6]，很显然

6 是 4的子节点，但4 < 6，不符合大顶堆的性质，那么也就是说：

我们每次在数组尾部添加了一个新元素，需要重新维护数组中元素的顺序来保证堆的性质

调整位置以保证堆的性质(12min)

首先，我们来看一个插入元素的过程动画

在这个动画中，我们可以观察到，我们在堆的尾部添加了一个元素这个元素是不符合大顶堆的性质的，于是我们会对元素的位置进行调整。

可以比较清楚的发现，调整过程中，新插入元素一直在不停的与他的父亲节点交换，直到整棵完全二叉树合法

于是，我们可以这样编码：

1	heap[++len] = val; // heap为堆数组，len为当前长度， val为新插入的元素，该步骤实现在尾部插入新元素
2	int temp_pos = len; //定义临时变量存储新添加元素当前的位置
3	while(temp_pos > 1 && heap[temp_pos] > heap[temp_pos / 2])// temp_pos > 1 保证了当前位置节点有父节点，根据完全二叉树性质，我们不难推断：一个节点的父节点标号=当前节点标号/2，heap[temp_pos] > heap[temp_pos / 2]保证了当前元素还没有到达合适位置
4	{
5	swap(a[temp_pos], a[temp_pos/2]); //交换当前节点与父节点
6	temp_pos /= 2; // 更新元素的当前位置
7	}

从堆中取出一个最大值(15min)

将首部元素取出(0.5min)

一般情况下，对我们有用的元素往往是根节点的值（也就是最值），

因此，我们要取出最大值，首先要将首部元素提出。

将尾部元素调整至首部(0.5min)

首部元素提出后，首部位置将会闲置，为了保证堆仍然是一颗完全二叉树，我们将尾部元素调整至首部

调整位置以保证堆得性质(14min)

同样的，调整之后堆的性质将被打乱，我们需要重新将首部元素调整至合适位置以保证堆的性质

我们来看一下删除元素的动画

从动画中我们可以看出，将尾部调整至首部后，首部元素不符合堆的性质，因此不断与比本身大的子节点交换（两个子节点都比本身大时与较大的子节点交换），直至整个堆合法。

因此，我们可以这样编码

int maxn = heap[1]; // 取出最大值，赋值给maxn
heap[1] = heap[len--]; // 将尾部元素调至首部，并改变堆的大小
int temp_pos = 1; // temp_pos 表示首部元素的当前位置
while(temp_pos * 2 <= len) // 保证当前节点有子节点
{
    if(temp_pos*2+1<=len) // 如果当前节点有两个子节点
    {
    	if(heap[temp_pos*2]>=heap[temp_pos*2+1]&&heap[temp_pos*2]>=heap[temp_pos])
        // 如果左子节点是两个子节点中最大的
            swap(heap[temp_pos*2],heap[temp_pos]),temp_pos=temp_pos*2; // 交换当前节点与左子节点
        else if (heap[temp_pos*2+1]>=heap[temp_pos*2]&&heap[temp_pos*2+1]>=heap[temp_pos])
        // 如果右子节点是两个子节点中最大的
            swap(heap[temp_pos*2+1],heap[temp_pos]),temp_pos=temp_pos*2+1; // 交换当前节点与右子节点
        else break; // 除此之外，表明堆已合法
    }
    else // 如果当前节点有一个子节点
    {
        if(heap[temp_pos*2] >= heap[temp_pos]) //如果子节点大于当前节点
            swap(heap[temp_pos*2], heap[temp_pos]),temp_pos=temp_pos*2; //交换当前节点与子节点
        else break; // 除此之外，表明堆已合法
    }
}

*线性建堆

至此，堆的基本内容已经给大家讲完了，已经了解时间复杂度的大家可以对堆的建立，删除，插入进行一个简单的分析，其实不难得出，一次插入与删除的复杂度均为O（log n）

现在，我们有n个元素，如果我们用上面所介绍的方法建堆，将插入n次，每次复杂度为O（log n），总复杂度为O（n*log n）

事实上，我们有线性时间建堆的方法，即复杂度O（n）的建堆方法

下面我们通过动画了解一下：

通过动画我们可以发现，线性建堆的方法，在于一开始即将无序的元素放入堆数组中，

然后从尾部元素开始，逐个向下调整（过程类似于删除首部元素后的调整），直到首部元素向下调整的过程结束，

一个符合堆性质的堆数组即建立完成

下面通过伪代码的方式给大家呈现整个过程的编码实现：

1	for(int i = len; i >= 1; i--){
2	if(i * 2 > len)continue; // 无子节点时直接跳过
3	down(i); //向下调整
4	}

其中down()函数不再给出，具体实现请大家参考从堆中取出最大值的操作。

编码完了，我们还有一个问题没有解决，即：

为什么这样操作的复杂度是O（n）的？

关于这个问题感兴趣的同学可以移步线性建堆复杂度证明去了解一下，在这里不做赘述

使用堆来排序(4.5min)

排序过程中，不断从堆顶（即根节点取出元素）即可，伪代码如下：

1	int p[N], len = 0;
2	while(heap不为空){
3	p[++len] = 取出堆顶();
4	}

使用堆来找出一个集合中的最值(0.5min)

建好堆后获取根节点的值即可

哈夫曼树(10min)

*什么是哈夫曼树(5min)

给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。

*如何构建一颗哈夫曼树(3min)

可以通过将元素压入小顶堆，每次取出两个元素，权值相加作为两个元素的根节点，同时将根节点压入堆中，直到堆中只剩下一个元素，则哈夫曼树建成

哈夫曼树有什么用(2min)

一道经典的例题：SDUTOJ 树-堆结构练习——合并果子之哈夫曼树

解题思路：

因为哈夫曼树是带权路径长度最短的树，所以本题可以通过构建哈夫曼树的思路解决，即：

将所有元素压入小顶堆中，每次取出两个元素相加，压入堆，直到堆中只剩一个元素，则该元素为最终答案

参考资料

堆排序中建堆过程的时间复杂度O(n)的证明

百度百科：堆

百度百科：哈夫曼树

SDUTOJ 树-堆结构练习——合并果子之哈夫曼树

可视化数据结构学习VisuAlgo—二叉堆

1	int maxn = heap[1]; // 取出最大值，赋值给maxn
2	heap[1] = heap[len--]; // 将尾部元素调至首部，并改变堆的大小
3	int temp_pos = 1; // temp_pos 表示首部元素的当前位置
4	while(temp_pos * 2 <= len) // 保证当前节点有子节点
5	{
6	if(temp_pos*2+1<=len) // 如果当前节点有两个子节点
7	{
8	if(heap[temp_pos2]>=heap[temp_pos2+1]&&heap[temp_pos*2]>=heap[temp_pos])
9	// 如果左子节点是两个子节点中最大的
10	swap(heap[temp_pos2],heap[temp_pos]),temp_pos=temp_pos2; // 交换当前节点与左子节点
11	else if (heap[temp_pos2+1]>=heap[temp_pos2]&&heap[temp_pos*2+1]>=heap[temp_pos])
12	// 如果右子节点是两个子节点中最大的
13	swap(heap[temp_pos2+1],heap[temp_pos]),temp_pos=temp_pos2+1; // 交换当前节点与右子节点
14	else break; // 除此之外，表明堆已合法
15	}
16	else // 如果当前节点有一个子节点
17	{
18	if(heap[temp_pos*2] >= heap[temp_pos]) //如果子节点大于当前节点
19	swap(heap[temp_pos2], heap[temp_pos]),temp_pos=temp_pos2; //交换当前节点与子节点
20	else break; // 除此之外，表明堆已合法
21	}
22	}