huffman-code - 构建规范霍夫曼树的最有效(*)方法是什么？

Question

假设 A 是一个数组，其中 A[0] 保存字母表中第 0 个字母的频率。

计算代码长度的最有效 (*) 方法是什么？不确定，但我想效率可能与内存使用或所需步骤有关。

我感兴趣的是数组 L，其中 L[0] 包含字母表中第 0 个字母的代码长度(位数)，其中代码来自由 A 频率阵列构建的规范哈夫曼树。

Answer 1

如果频率形成单调序列，即。 A[0]<=A[1]<=...<=A[n-1] 或 A[0]>=A[1]>=...>=A[n-1], 那么你可以在 O(n) 时间和 O(1) 额外空间内生成最佳代码长度。该算法只需要对数组进行 2 次简单传递，而且速度非常快。 [1] 中给出了完整的描述。

如果您的频率未排序，首先您需要对它们进行排序，然后应用上述算法。在这种情况下，时间复杂度为 O(n log n)，并且需要一个包含 n 个整数的辅助数组来存储排序顺序 - 空间复杂度为 O(n)。

[1]:Alistair Moffat 和 Jyrki Katajainen 的最小冗余代码就地计算，在线提供:http://www.diku.dk/~jyrki/Paper/WADS95.pdf