哈夫曼(Huffman)树

引入：带权路径长度wpl

树 $T$ 有 $n$ 个叶子结点，若结点 $k$ 的权值为$w_k$ ，到根结点的路径长为 $l_k$ ，那么结点 $k$ 的值为 $w_k \times l_k$，树 $T$ 所有叶子结点的值之和记作 $wpl(T)$。

问题

给定实数 $p_1,p_2,\cdots,p_n$ ，找一组由“0”或“1”组成的字符串 $S_1,S_2,\cdots,S_n$ 使得：

1. 这 $n$ 个字符串彼此不为前缀，
2. 使 $\sum_{i=1}^n p_n|S_n|$ 最小。

例题：P1090合并果子

描述

给定 $n$ 个实数 $w_1,w_2,\cdots,w_n$ ，构造一棵有 $n$ 个叶子结点的二叉树 $T$ ，使得所有叶子结点的权值分别为 $w_1,w_2,\cdots,w_n$ ，那么wpl最小的那些树称为Huffman树。

我们定义 $W=\{w_1,w_2,\cdots,w_n\}$ , $wpl(W)=\min wpl(T)$ , 其中树 $T$ 有 $n$ 个叶子结点，所有叶子结点的权值分别为 $w_1,w_2,...,w_n$ 。

当 $|W|>1$ 时，定义 $W'=(W-\{w_i,w_j\})\cup\{w_i+w_j\}$ ，那么 $wpl(W)=wpl(W')+w_i+w_j$ 。其中 $w_i,w_j$ 为 $W$ 中最小的两个数。

应用：Huffman编码

发电报： 将明文编码为01串，根据字符出现的频率编码，使电文总长最短。

思路1：等长编码 思路2：根据Huffman树编码