定义

对于二路的最佳归并数，就是 哈夫曼树。这里就不多赘述了。这里重点讲讲多路归并的情况。

普通的哈夫曼树，构建流程是每次选择最小的节点进行合并，那么对于多路 k 路归并，那么就每次选取最小的前 k 个数进行合并即可。
对于初始序列 [2,3,6,17,24,18,9,30,12]，构建出的 3 路归并哈夫曼树如下所示：

添加虚段

但是这里有一个问题，如果初始序列的个数不是 3 的倍数又如何合并呢？例如，只有 8 个元素。可以想到，我们只要补充一个 0 号序列充数就可以了。这个充数的元素称为虚段。

拓展一下，如果是 k 叉归并，初始段中共有 m 个序列，那么总共要补充多少 0 元素呢？

对于一颗严格的 k 叉哈夫曼树，只有度数为 k 的点和度数为 0 的点，那么就有如下式子：

上面的 ${\displaystyle n_k}$ 一定是整数。从而，需要补充 ${\displaystyle (k-1)-u}$ 个虚段。