笔记 - Huffman 树与 Huffman 编码

Huffman 编码是一种基于 Huffman 树的,按字符概率构造的,能保证编码平均长度最短的编码方式

https://cplib.tifa-233.com/src/code/util/huffman_tree.hpp 存放了笔者对该算法 / 数据结构的最新实现,建议前往此处查看相关代码

介绍

Huffman 树即为根结点到所有叶子结点的带权路径长度之和最小的树

构建方式

对于一棵 \(k\) 叉的 Huffman 树,我们首先要确保 结点个数 \(n\) 满足 \((k-1)\mid(n-1)\), 否则我们可以补充若干个权值为 \(0\) 的结点使其成立

首先按结点的权值排序,然后取出 \(k\) 个权值最小的结点合并为一个新结点并插入该序列,新结点的权值为这 \(k\) 个点权值之和,直到序列中只剩下 \(1\) 个结点为止

Huffman 编码通过对 Huffman 树进行层序遍历得到

例题

代码 (K 叉 Huffman 树)

Show code