CSP-J 2021 第一轮 第 11 题：哈夫曼编码的本质策略

题目

在数据压缩编码中的哈夫曼编码方法，在本质上是一种（  ）的策略。

选项

• A. 枚举
• B. 贪心
• C. 递归
• D. 动态规划

答案

B

题解

答案是 B. 贪心。

哈夫曼编码的构造过程是：

1. 每次选出当前权值（出现频率）最小的两个节点。
2. 将它们合并成一个新节点，权值为两者之和。
3. 把新节点放回，重复上述过程，直到只剩下一个根节点。

它每一步都选择当前权值最小的两个节点，通过这样的局部最优选择，最终得到整体最优的编码，因此本质上采用的是贪心策略。