8-15外部排序-最佳归并树

文件通过置换-选择排序后，得到了长度不等的初始归并段，通过最佳归并树来组织这些归并段，使得I/O最小

一.归并树

数字表示该归并段占的磁盘块数量

对初始归并段进行二路归并

合并R2和R1需要将5+1=6块的数据读入内存，需要读磁盘6次；将合并后的新归并段写回磁盘，需要6次的写操作

6和8的归并同样，需要读写各6+8=14次

完成

共需要读写各6+8+14+16=44次

将其看成是一棵二叉树，可以算的WPL=2×1+(5+1+6+2)×3=44=读磁盘次数=写磁盘次数

因此归并过程中的磁盘I/O次数=归并树的WPL×2

二.最佳归并树

1.二路归并使用哈夫曼树

此时WPL=6×1+5×2+2×3+(1+2)×4=34
读磁盘数=写磁盘数-34，总的磁盘I/O次数=68

2.多路归并：类似于哈夫曼树

（1）以3路归并段为例
对于

构造

归并过程中磁盘I/O次数446次

注：若减少一个归并段

初始

错误构造

可以看出，最后一次归并只是两路，不满足要求

因此，需要补充几个长度为0的“虚段”。

本题中添加一个长度为0的归并段，在构造k叉哈夫曼树时按0计算。

可以看出，度为0的结点数量等于初始归并段的个数

（2）计算添加虚段的个数

k叉最佳归并树应该只有度为0和度为k的结点，因此有n₀+n_k=n ①。又因为每个结点都带有一个叉，n_k个分支结点的度均为k，共有k×n_k个叉。除根结点外，每个结点都带有一个叉，因此k×n_k=n-1 ②

联立①②有$n_k=\frac{n_0-1}{k-1}$

因为n_k是整数，因此$\frac{n_0-1}{k-1}$也是整数

因此，若
(初始归并段的数量n₀-1)%(k-1)=0，说明刚好可以构成严格k叉树
若
(初始归并段的数量n₀-1)%(k-1)=u，说明需要补充(k-1-u)个虚段

如初始归并段数量为19的，构造8路归并，则需要补充3个虚段