Huffman 树

Huffman 树

前缀无关编码 PFC

每个字符作为一个叶节点，从根到字符的通路即为字符的编码

编码长度 CL

• 对每个字符而言，编码长度是叶节点的深度
• 对整体而言，编码长度是所有字符的编码长度之和

最优编码树 OCT

• CL 最短的编码树
• 必然存在，但未必唯一
• 真的完全树即是 OCT
• OCT 的叶子只能出现在倒数两层（完全树），否则，交换更高的叶节点和倒数第二层的内部节点，CL 必然减小

带权编码长度 WCT

对字符的频数进行加权，此时 OWCT 未必是完全树。 频数高的字符尽可能放在高处。 未必唯一，树高也未必相同，两个权重相同的节点位置可以互换。

Huffman 树策略

约定左兄弟不小于右兄弟 贪心策略：反复取权重最小的两颗树，合并为一颗树，权重取二者之和。

正确性

权重最小的两个节点必定在某个 OWCT 中是兄弟。 数学归纳法：

• 若对于所有 $|\Sigma |<n$ 均正确，考虑 $|\Sigma |=n$
• $x,y$ 为最小的节点，引入节点 $z$，使 $w(z)=w(x)+w(y)$，得到字符集 $\Pi =\Sigma \setminus \{x,y\}\cup \{z\}$
• 则 $\Sigma$ 中所有 $x,y$ 为兄弟的编码树与 $\Pi$ 中的编码树一一对应，且 $WCL(\sigma )-WCL(\pi )\equiv w(z)$
• 则 $\Sigma$ 的最优编码树对应于 $\Pi$ 中的最优编码树，由归纳假设知命题成立

实现

• 向量和列表的直接实现均需 $O(n^2)$，主要瓶颈在于插入或查找最大值
• 可以用优先队列实现，$O(n\log n)$
• 可以用一个队列加一个栈实现，先 $O(n\log n)$ 进行排序，从大到小压入栈中，另外维护一个有序队列，则每次只可能从栈顶或队首取数，相加后加入队列，每次操作为 $O(1)$，总时间复杂度为 $O(n\log n)$