最佳归并树解决什么问题

在外部排序中，各初始归并段长度可能不同。若归并顺序安排不好，较长的归并段可能被反复读写很多次，导致磁盘 I/O 增加。

最佳归并树用于安排归并顺序，使总读写代价最小。

基本思想和哈夫曼树相同：

二路最佳归并树

二路归并时，每次选两个权值最小的归并段先归并。

例如初始归并段长度为：

$$
2,\ 3,\ 6,\ 9
$$

构造过程：

所有内部结点权值之和为：

$$
5+11+20=36
$$

这个值就是归并过程中每个记录块被反复参与归并的总次数，也等于最佳归并树的带权路径长度。

若权值表示磁盘块数，则：

$$
\text{读磁盘次数}=36,\qquad \text{写磁盘次数}=36
$$

所以总磁盘 I/O 次数为：

$$
72
$$

$k$ 路归并时，每次应选 $k$ 个权值最小的归并段归并。

但 $k$ 路最佳归并树必须是严格 $k$ 叉树：

如果初始归并段数量不满足严格 $k$ 叉树的叶子数条件，就需要补充权值为 $0$ 的虚段。

设初始归并段数量为 $r$，归并路数为 $k$。

若：

$$
(r-1)\bmod(k-1)=0
$$

则刚好能构成严格 $k$ 叉树，不需要补虚段。

若：

$$
(r-1)\bmod(k-1)=u\ne0
$$

则需要补充：

$$
(k-1)-u
$$

个虚段。

为什么看 $(r-1)\bmod(k-1)$

严格 $k$ 叉树中，若内部结点数为 $n_k$，叶结点数为 $n_0$，则有 $n_0=(k-1)n_k+1$。因此叶结点数量必须满足 $(n_0-1)$ 能被 $(k-1)$ 整除。

# 三路归并例子

若有 $8$ 个初始归并段，采用 $3$ 路最佳归并树：

$$
(8-1)\bmod(3-1)=7\bmod2=1
$$

需要补充：

$$
(3-1)-1=1
$$

个虚段。

然后把这个虚段作为权值 $0$ 的叶结点，与其他归并段一起按三路哈夫曼思想构造：每次取三个最小权值合并。