在附加某些特定条件之后,问题的难度往往会有实质的下降。比如,若待编码字符集已按出现频率排序,则Huffman编码可以更快完成。在编码过程中,始终将森林<img src='https://img2.soutiyun.com/ask/2021-01-29/98077884085937.jpg' />中的树分为两类:单节点(尚未参与合并)和多节点(已合并过)。每经过一次迭代,后者虽不见得增多,但必然有一个新成员。

a)试证明,在后一类树中,新成员的权重(频率)总是最大; b)试利用以上性质设计一个算法,在O(n)时间内完成Huffman编码。

时间:2024-04-03 13:28:29

相似题目