哈夫曼树与哈夫曼编码

发表于2026-03-09|更新于2026-03-09|算法·理论

|浏览量:

哈夫曼树：

哈夫曼树可由如下方式构造：

由给定的 $n$ 个权值构造 $n$ 棵仅含有一个根结点的二叉树，记作集合 $F$。
从集合 $F$ 中选取根结点权值最小的两棵二叉树 $T1$，$T2$ 作为左右子树构造新的二叉树 $T3$，新二叉树的根结点为 $T1$，$T2$ 根结点的权值和。
从集合 $F$ 中删除 $T1$，$T2$，将 $T3$ 加入 $F$ 中。
直到 $F$ 中只剩下唯一一棵二叉树为止，这棵树即为哈夫曼树。

建树：

字符	频率	编码	长度
A	35	11	2
B	25	00	2
C	15	01	2
D	15	101	3
E	10	100	3

哈夫曼编码：

哈夫曼编码根据字符在数据中出现的频率来分配不同长度的编码，频率高的字符分配较短的编码，频率低的字符分配较长的编码，从而实现压缩数据的目的，是一种贪心思想。

哈夫曼编码是一种前缀编码，即任一编码都不是其他任何一个编码的前缀。哈夫曼编码即为前缀编码中最短的。

带权路径长度(WPL)。

WPL 是每个编码的长度 $\times$ 频率。

字符	频率	编码	长度	WPL(单个的)
A	35	11	2	70
B	25	00	2	50
C	15	01	2	30
D	15	101	3	45
E	10	100	3	30

WPL（总共的）$=70+50+30+45+30=225$。

文章作者: heyZzz

文章链接: https://heyzzz629.github.io/2026/03/09/%E5%93%88%E5%A4%AB%E6%9B%BC%E6%A0%91%E4%B8%8E%E5%93%88%E5%A4%AB%E6%9B%BC%E7%BC%96%E7%A0%81/

版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 heyZzz's OI Blog！

算法哈夫曼树与哈夫曼编码

相关推荐

矩阵加速递推

PS：本文章因篇幅有限，就不讲矩阵乘法和快速幂了。题目： $$F_n = \left{\begin{aligned} 1 \space (n \le 2) \ F_{n-1}+F_{n-2} \space (n\ge 3) \end{aligned}\right.$$ 求 $F_n$。定义一个矩阵$[Base]$，使： $$\begin{bmatrix}F_n,F_{n+1}\end{bmatrix}\times\begin{bmatrix}Base\end{bmatrix}=\begin{bmatrix}F_{n+1},F_{n+2}\end{bmatrix}$$ 那： $$\begin{bmatrix}F_n,F_{n+1}\end{bmatrix}\times\begin{bmatrix}Base\end{bmatrix}^2=\begin{bmatrix}F_{n+2},F_{n+3}\end{bmatrix}$$ $$\begin{bmatrix}F_n,F_{n+1}\end{bmatrix}\times\begin{bmatrix}Base\end{bmatri...

ST表 ST表它是解决 RMQ 问题（区间最值问题）的一种强有力的工具。时间复杂度为 $O(n \log n+Q)$。实现过程 PS：以下讨论的是最大值，最小值同理。建立一个 $dp$ 数组 $dp_{i,j}$ 表示从 $i$ 开始 $2^j$ 个数中的最大值。边界为 $dp_{i,0}=a_i$，即从 $i$ 点开始 $2^0$ 个数中的最大值。我们不难发现 $\max{\max{a_1 … a_{\frac{n}{2}}},\max{a_{\frac{n}{2}} … a_n}}}=\max{a_1…a_n}$。那状态转移方程为： $dp_{i,j}=\max{dp_{i,j-1},dp_{i+2^{j-1},j-1}}$。其中 $dp_{i,j-1}$ 是前面一段，$dp_{i+2^{j-1},j-1}$ 是后面一段。求最值将该区间分成两个ST表，然后直接维护的小区间，然后二者求最值即可。就是：$\max{f_{l,k},f[r−(2^k)+1][k]}$。

排序的稳定性

排序的稳定性排序算法平均时间复杂度最好时间复杂度最坏时间复杂度空间复杂度是否稳定冒泡排序 $O(n^2)$ $O(n)$ $O(n^2)$ $O(1)$ $T$ 选择排序 $O(n^2)$ $O(n^2)$ $O(n^2)$ $O(1)$ $F$ 插入排序 $O(n^2)$ $O(n)$ $O(n^2)$ $O(1)$ $T$ 归并排序 $O(nlogn)$ $O(nlogn)$ $O(nlogn)$ $O(n)$ $T$ 快速排序 $O(nlogn)$ $O(nlogn)$ $O(n^2)$ $O(log~n)$ $F$ 堆排序 $O(nlogn)$ $O(nlogn)$ $O(nlogn)$ $O(1)$ $F$ 希尔排序 $O(nlogn)$ $O(n)$ $O(n^2)$ $O(1)$ $F$ 计数排序 $O(n+k)$ $O(n+k)$ $O(n+k)$ $O(n+k)$ $T$ 基数排序 $O(n \times m)$ $O(n \times m)$ $O(n \times m)$ $O(m)$ $T$ ...