哈夫曼树
定义
给定\(n\)个权值作为\(n\)个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树 (Huffman Tree)。
有关概念
结点的带权路径长度：从根结点到该结点的路径长度与该结点的权值之积；
树的带权路径长度（WPL）：树上所有叶子结点的带权路径长度之和。
构造方法
思路
给定\(n\)个权值，分别为\(\{w_1,w_2,\dots,w_n\}\) :
- 构造\(n\)棵每棵只有一个结点的树，树的权值为给定权值；
- 构建一棵新树，从现有森林中选出权值最小的两棵树，作为新树的左右子树，新树的权值为两棵子树的权值和；
- 删除原有的两棵树，将新树加入森林；
- 重复 2、3 两步直到森林中只有一棵树。
实例
应用——哈夫曼编码
定义
霍夫曼编码 (Huffman Coding)，又译为哈夫曼编码、赫夫曼编码，是一种用于无损数据压缩的熵编码（权编码）算法。
有关概念
- 二进制编码：用预先规定的方法将文字、数字或其他对象编成二进制的数码。
- 等长码：采用相同长度的不同二进制码代表相应的对象。这种编码的特点是译码简单且具有唯一性，但编码长度并不是最短的。
- 变长码：相对于等长码。设计变长码需要保证唯一性，但是编码长度可能更短。
- 熵编码：熵编码法是一种独立于介质的具体特征的进行无损数据压缩的方案。
一种主要类型的熵编码方式是对输入的每一个符号，创建并分配一个唯一的前缀码，然后，通过将每个固定长度的输入符号替换成相应的可变长度前缀无关（prefix-free）输出码字替换，从而达到压缩数据的目的。每个码字的长度近似与概率的负对数成比例。因此，最常见的符号使用最短的码。
实现
思路
- 构造哈夫曼树，结点权值为该符号出现的频率（次数）；
- 每个结点向左子树的边记为‘0’，向右子树的边记为‘1’；
- 该符号的编码即为从根节点到该符号所对应的叶节点路径形成的 01 字符串。
实例
原字符：
之前样例里的哈夫曼树即为构造出来的哈夫曼树。
构造后哈夫曼编码：
