贪心算法之哈夫曼编码

哈夫曼编码是一种贪心算法，用于将字符集中的字符进行编码，使得编码后的平均码长最短。它是一种前缀码，即任何一个字符的编码都不是其他字符编码的前缀。

下面是哈夫曼编码的步骤：
1. 统计字符集中每个字符出现的频率，并将每个字符作为一个独立的树叶。
2. 将这些树叶按照频率从小到大排序。
3. 从频率最小的两个树叶中选择一个根节点，频率较小的作为左子树，频率较大的作为右子树，构建一棵新的树。
4. 将新构建的树插入到原来的树叶列表中，并保持列表有序。
5. 重复步骤3和步骤4，直到只剩下一个树。
6. 最后剩下的树即为哈夫曼树，树中的每个叶子节点对应一个字符，从根节点到叶子节点的路径上的0和1分别表示编码中的0和1。
7. 根据哈夫曼树生成每个字符的编码。

以下是一个示例：
假设字符集为{'A': 5, 'B': 9, 'C': 12, 'D': 13, 'E': 16, 'F': 45}，其中每个字符的频率已经给出。

1. 构建初始的树叶列表：[('A', 5), ('B', 9), ('C', 12), ('D', 13), ('E', 16), ('F', 45)]
2. 选择频率最小的两个树叶'A'和'B'，构建新的树：[('AB', 14), ('C', 12), ('D', 13), ('E', 16), ('F', 45)]
3. 选择频率最小的两个树叶'C'和'D'，构建新的树：[('AB', 14), ('CD', 25), ('E', 16), ('F', 45)]
4. 选择频率最小的两个树叶'E'和'AB'，构建新的树：[('ABE', 30), ('CD', 25), ('F', 45)]
5. 选择频率最小的两个树叶'CD'和'ABE'，构建新的树：[('ABECD', 55), ('F', 45)]
6. 最后剩下的树为：[('ABECD', 55), ('F', 45)]

根据哈夫曼树生成的编码如下：
A: 00
B: 01
C: 10
D: 11
E: 110
F: 111