假设我有许多重复的条目要合并到霍夫曼编码树中。简单地合并它们将花费 n*logn 但我希望它更快。假设我有 100000 个相同频率 1 的条目，那么暴力哈夫曼树构建将合并 一开始50000次，很慢。
老师告诉我，我们可以直接认为是(2,50000)、(4, 25000)等等，这样就快多了。但我不知道如何实施它。 （Cpp 代码的解释会对我有很大帮助；）
如果你所有的“条目”（我认为是符号）具有相同的频率，那么你根本不需要构建霍夫曼树。
给定 n 符号，找到 2 的最大幂，称为 k，使得 k ≤ n。然后使用 lg k 位对前 2k - n 符号进行编码，并使用 1 + lg k 位对剩余的 2(n - k) 符号进行编码。您可以通过在第二组符号的末尾附加一位来使其成为前缀代码。
因此，如果 n = 5，则有 k = 4 和 lg k = 2。前三个符号使用两位进行编码：
00
01
10
剩下的两个符号用三位编码，在前面的两位编码递增后在右边添加一位：
110
111