目录

一、大顶堆与小顶堆

1.大顶堆与小顶堆的概念

2.大顶堆的构建

二、哈夫曼树

1.哈夫曼树的定义

2.基本概念

3.构造哈夫曼树

4.哈夫曼编码

---

一、大顶堆与小顶堆

1.大顶堆与小顶堆的概念

大顶堆：每个结点的值都大于或等于其左右孩子结点的值。

小顶堆：每个结点的值都小于或等于其左右孩子结点的值。

2.大顶堆的构建

以数组A=（2，8，7，1，3，5，6，4）为例，先根据数组，还原一棵二叉树。

先找到最后一个非叶子结点，数组的长度为8，则最后一个非叶子结点是8/2-1=3，然后比较结点值和它的子树值，如果该结点小于其左/右子树的值，交换。

因为1小于它的左子树的值4，所以交换1和4。

 继续找下一个非叶子结点，就是当前位置3（下标）减1，下标为2。

因为7大于左子树的值5，不交换。

继续找下一个非叶子结点，下标为1。

因为8大于左子树的值4，不交换。

继续找下一个非叶子结点，下标为0。

因为2不大于8也不大于7，所要重调，交换2和8。

重新调整：从下标为3的非叶子结点开始，因为4大于它的左子树值1，不交换，

继续找下一个非叶子结点，当前位置3下标减1，下标为2。

因为7大于它的左子树值5和右子树值6，不交换，

继续找下一个非叶子结点，当前位置2下标减1，下标为1。

因为2不大于它的左子树值4，所以交换2和4。

 继续找下一个非叶子结点，当前位置1下标减1，下标为0。

因为8大于它的左子树值4和右子树值7，不交换。

左右结点都满足大顶堆的性质，大顶堆建立完成。

数组A=（2，8，7，1，3，5，6，4）的大顶堆序列为8、4、7、2、3、5、6、1。

例题：（2021下半年上午真题60）

n个关键码构成的序列{k,k2, ...K,}当且仅当满足下列关系时称其为堆。

以下关键码序列中，( ) 不是堆。

A、15,25,21,53,73,65,33

B、15,25,21,33,73,65,53

C、73,65,25,21,15,53,33

D、73,65,25,33,53,15,21

所属知识点：数据结构与算法基础>排序

答案解析：

本题考查堆排序的算法问题。

堆分为大顶堆（根节点大于左孩子和右孩子节点）和小顶堆（根节点小于左孩子节点和右孩子节点）。

根据选项来看，共7个节点，应该是3层的满二叉树，符合堆的有A，B，D三个选项。

仅有C选项73,65,25,21,15,53,33,73作为根节点，根大于其左孩子节点65和右孩子节点25都，是大顶堆的构造，第二层65作为左子树的根节点，大于了其左孩子节点21和右孩子节点15，符合大顶堆的构造；25作为右子树的根节点，却小于了其左孩子节点53和右孩子节点33，不符合大顶堆的构造了，故其不是堆。 

简洁解释：

A选项，根据数组，还原一棵二叉树如下，根结点全都小于左右子树，是小顶堆。

B选项，根据数组，还原一棵二叉树如下，根结点全都小于左右子树，是小顶堆。

 

  C选项，根据数组，还原一棵二叉树如下，73和65符合大顶堆的构造，但25不符合。

 

 D选项，根据数组，还原一棵二叉树如下，根结点全都大于左右子树，是大顶堆。

 

二、哈夫曼树

1.哈夫曼树的定义

哈夫曼树也称最优二叉树，即给定n个权值作为n个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。

2.基本概念

树的路径长度：从树根到每一个叶子结点之间的路径长度之和。

树的带权路径长度(WPL)：所有叶子结点的带权路径长度之和。

3.构造哈夫曼树

将每个结点的权重按从小到大的顺序排队。

把两个最小的权重相加，并继续这一步骤，始终将较高的权重分支放在右边，直到加完所有结点的权重。

画出由根结点到每个叶子结点的路径，顺序记下沿路径的０和１，所得就是该符号的哈夫曼码字。

例子：有6个结点，权值分别为2,3,4,6,7,15，求树的带权路径长度，并画出构造的哈夫曼树。

例题：

由权值为 29、12、15、6、23 的五个叶子结点构造的哈夫曼树为（ ），其带权路径长度为（ ）。
（1）

 （2）A.85        B.188        C.192        D.222

所属知识点：数据结构与算法基础>树与二叉树的特性

答案解析：本题考查哈夫曼树。
构造最优二叉树的哈夫曼算法如下。
① 根据给定的n个权值｛w1， w2，…，Wn｝构成n棵二叉树的集合F= {T1.T2，…，Tn}，其中每棵树T;中只有一个带权为w;的根结点，其左右子树均空。
② 在F中选取两棵根结点的权值最小的树作为左右子树，构造一棵新的二叉树，置新构造二叉树的根结点的权值为其左、右子树根结点的权值之和。
③从F中删除这两棵树，同时将新得到的二叉树加入到F中。
重复②、③，直到F中只含一棵树时为止。这棵树便是最优二叉树（哈夫曼树）。从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径，路径上的分支数目称为路径长度。树的路径长度是从树根到每一个结点的路径长度之和。树的带权路径长度为树中所有叶子结点的带权路径长度之和。

一般来说，这题的6和12应该换位，小的数放左边，大的数放右边。

因此，其带权路径长度（12+6）*3+15*2+23*2+29*2=188。 

 4.哈夫曼编码

通过哈夫曼树构造的编码。

例题1：（2021下半年上午真题64-65）

已知一个文件中出现的各字符及其对应的频率如下表所示。采用Huffman编码，则该文件中字符a和c的码长分别为(1)。若采用Huffman编码，则字序列 “110001001101” 的编码应为(2)。

(1)A、1和3

B、1和4

C、3和3

D、3和4

(2)A、face

B、bace

C、acde

D、fade

所属知识点：数据结构与算法基础>最优二叉树（哈夫曼树）

答案解析：

本题考查哈夫曼树的构造问题。

根据题中表格字符构造出如下的哈夫曼树。

根据哈夫曼树可得：图中a的长度为1，c的长度为3。

第二空，a：0，b：101，c：100，d：111，e：1101，f：1100。

而对于字序列 “110001001101” 编码应该为face。

例题2：（2019下半年上午真题）

已知某文档包含5个字符，每个字符出现的频率如下表所示。采用霍夫曼编码对该文档压缩存储，则单词”cade“的编码为（ ），文档的压缩比为（ ）。

（1）A.1110110101        B.1100111101

C.1110110100        D.1100111100

（2）A.20%        B.25%        C.27%        D.30%

所属知识点：数据结构与算法基础>最优二叉树（哈夫曼树）

答案解析：解析1根据题干，可以先构造出如下哈夫曼树：

对应c的编码111，a的编码0，d的编码110，e的编码101，第一空选择A选项。
压缩前，若要表示5个不同的字符，用二进制编码至少需要3位二进制，即每位字符占据空间3bit，平均字符长度为：
3×40%+3×10%+3×20%+3×16%+3×14%=3；
压缩后，这5个字符的编码长度分别为1、3、3、3、3，平均编码长度为：
1×40%+3×10%+3×20%+3×16%+3×14%=2.2；
压缩比为（3-2.2）/3=27%。