8.7.5 最佳归并树
## 8.7.5 最佳归并树
文件经过置换-选择排序后，得到长度不等的初始归并段。下面讨论如何安排这些长度不等的归并段的归并顺序，使得I/O次数最少。假设通过置换-选择排序得到9个初始归并段，其长度依次为9,30,12,18,3,17,2,6,24。若采用3路平衡归并，一种可能的归并树如图8.18所示。
在图8.18中，各叶结点表示一个初始归并段，其上的权值表示该段的长度；叶结点到根的路径长度表示该段参与归并的趟数；非叶结点表示归并生成的新段；根结点对应最终有序文件。树的带权路径长度WPL等于归并过程中读取的总记录数，因此总的I/O次数 $= 2 \times \mathrm{WPL} = 484$ 。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图8.18 3路平衡归并的归并树 ## 考察说明 构造三叉呛夫曼树及相关的分析和计算（2013） 显然，不同的归并方案对应不同的归并树，其WPL（I/O次数）也不同。为最小化I/O开销，可将哈夫曼编码的思想推广至 $k$ 叉树情形：优先归并长度较小的段，延后归并长度较大的段，从而构造出I/O次数最少的最佳归并树。对上述9个归并段，按此原则构造的最佳3路归并树如图8.19所示，按此方案归并，总I/O次数仅为446，显著优于普通方案。 图8.19所示的归并树是一棵严格三叉树，即树中只有度为3或0的结点。然而，当初始归并段的数量不足以构成严格
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图8.19 3路平衡归并的最佳归并树 $k$ 叉树（也称正则 $k$ 叉树）时，直接进行 $k$ 路归并会导致某些归并轮次不足 $k$ 路，从而降低效率。例如，若只有8个初始归并段（如删除上例中长度为30的段），如果强行在最后一次归并时降为2路，其余仍为3路，则I/O次数将高达386，这并非最优方案。更优的做法是：引入若干长度为0的“虚段”（不包含实际数据的空归并段），使每趟归并都能满路（每次归并都处理3个段）。这些虚段不会产生实际的I/O开销，但能让归并树的结构更接近哈夫曼最优形态——权值较小的段（包括虚段）被安排在更深的位置，避免过早参与归并。按照这一思路构造的最佳归并树如图8.20所示，其I/O次数显著降低至326。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图8.20 8个归并段的最佳归并树
## 如何判定添加虚段的数目？
设度为0的结点有 $n_0$ 个，度为 $k$ 的结点有 $n_k$ 个，归并树的结点总数为 $n$，则有：
- $n = n_{k} + n_{0}$ （总结点数 $=$ 度为 $k$ 的结点数 $+$ 度为0的结点数）
- $n = k n_{k} + 1$ （总结点数 $=$ 所有结点的度数之和 $+1$）
因此，对严格 $k$ 叉树有 $n_0 = (k - 1)n_k + 1$，由此可得 $n_k = (n_0 - 1) / (k - 1)$。
接下来，根据 $n_0$ 和 $k$ 的关系，判断是否需要添加虚段：
- 若 $(n_0 - 1)\% (k - 1) = 0$ （%为取模运算），则说明这 $n_0$ 个叶结点（初始归并段）正好可以构成一棵严格的 $k$ 叉归并树。此时，内结点有 $n_k$ 个。
- 若 $(n_0 - 1)\% (k - 1) = u \neq 0$，则说明对于这 $n_0$ 个叶结点，其中有 $u$ 个多余，不能直接纳入 $k$ 叉归并树。为构造包含所有 $n_0$ 个初始归并段的 $k$ 叉归并树，应在原有 $n_k$ 个内结点的基础上再增加1个内结点。该内结点将代替一个叶结点的位置，被代替的叶结点连同多出的 $u$ 个叶结点，再加上 $k - u - 1$ 个空归并段，即可构建完整的归并树。
<!-- page: 397 -->
第8章 排序
385
# 要点追查 ▶ 实现最佳归并时需补充的虚段数量的分析（2019）
以图8.20为例，用8个归并段构造三叉树时，$(n_0 - 1)\% (k - 1) = (8 - 1)\% (3 - 1) = 1 \neq 0$，表明当前叶结点数无法构成严格的三叉树。因此，需要添加 $3 - 1 - 1 = 1$ 个虚段，使叶结点总数增至9，满足 $(9 - 1)\% (3 - 1) = 0$，这样就可以构建一棵完整的严格三叉树。
## 8.7.6 本节试题精选
### 一、单项选择题
01. 外部排序和内部排序的主要区别是（）。
A. 内部排序的数据量小，而外部排序的数据量大
B. 内部排序不涉及内、外存数据交换，而外部排序涉及内、外存数据交换
C. 内部排序的速度快，而外部排序的速度慢
D. 内部排序所需的内存小，而外部排序所需的内存大
02. 下列关于外部排序的说法中，正确的是（）。
A. 置换选择排序得到的初始归并段的长度一定相等
B. 内外存交换数据的时间只占总排序时间的一小部分
C. 败者树是一棵完全二叉树
D. 外部排序不涉及对文件的读/写操作
03. 多路平衡归并的作用是（）。
A. 减少归并越数
B. 减少初始归并段的个数
C. 便于实现账者树
D. 以上都对
04. 设在磁盘上存放有 375000 个记录，进行 5 路平衡归并排序，内存工作区能容纳 600 个记录，为把所有记录排好序，需要进行（）越归并排序。
A. 3
B. 4
C. 5
D. 6
05. 在下列关于外部排序过程输入/输出缓冲区作用的叙述中，不正确的是（）。
A. 暂存输入/输出记录
B. 内部归并的工作区
C. 产生初始归并段的工作区
D. 传送用户界面的消息
06. 若只需 3 越排序就可完成 64 个元素的多路归并排序，则选取的归并路数最少是（）。
A. 2
B. 3
C. 4
D. 5
07. 置换-选择排序的作用是（）。
A. 用于生成外部排序的初始归并段
B. 完成将一个磁盘文件排序成有序文件的有效的外部排序算法
C. 生成的初始归并段的长度是内存工作区的2倍
D. 对外部排序中输入/归并/输出的并行处理
08. 一个无序文件的 $n$ 个记录采用置换选择排序产生 $m$ 个有序段，则 $m$ 和 $n$ 的关系是（）。
A. $m$ 与 $n$ 成正比
B. $m = \log_2 n$
C. $m$ 与 $n$ 成反比
D. 以上都不对
09. 在由 $k$ 路归并构建的账者树中选取一个关键字最小的记录，则所需时间为（）。
A. $O(1)$
B. $O(k)$
C. $O(\log_2 k)$
D. 以上都不对
10. 下列关于小顶堆和账者树的说法中，正确的是（）。
I. 账者树从下往上维护，每上一层，只需和失败结点比较1次
II. 账者树的每次维护，必定要从叶结点一直走到根结点，不可能从中间停止
III. 堆从上往下维护，每下一层，若其左右孩子均不为空，则需比较2次
<!-- page: 398 -->
2027年数据结构考研复习指导
IV. 堆的每次维护，必定要从根结点一直走到叶结点，不可能从中间停止
A. I、III
B. II、III
C. I、II、III
D. I、III、IV
11. 最佳归并树在外部排序中的作用是（）。
A. 完成 $m$ 路归并排序
B. 设计 $m$ 路归并排序的优化方案
C. 产生初始归并段
D. 与锦标赛树的作用类似
12. 在由 $m$ 个初始归并段构建的 $k$ 阶最佳归并树中，不需要补充虚段，则度为 $k$ 的结点个数是（）。
A. $(m - 1) / k$
B. $m / k$
C. $(m - 1) / (k - 1)$
D. 无法确定
13. 【2013统考真题】已知三又树 $T$ 中6个叶结点的权分别是2,3,4,5,6,7，$T$ 的带权（外部）路径长度最小是（）。
A. 27
B. 46
C. 54
D. 56
14. 【2016统考真题】对10TB的数据文件进行排序，应使用的方法是（）。
A. 希尔排序
B. 堆排序
C. 快速排序
D. 归并排序
15. 【2019统考真题】设外存上有120个初始归并段，进行12路归并时，为实现最佳归并，需要补充的虚段个数是（）。
A. 1
B. 2
C. 3
D. 4
16. 【2024统考真题】在外排序中，利用账者树对初始为升序的归并段进行多路归并，账者树中记录“冠军”的结点保存的是（）。
A. 最大关键字
B. 最小关键字
C. 最大关键字所在的归并段号
D. 最小关键字所在的归并段号
## 二、综合应用题
01. 若某个文件经内部排序得到80个初始归并段，试问：
1）若使用多路平衡归并执行3越完成排序，则应取得的归并路数至少应为多少？
2）若操作系统要求一个程序同时可用的输入/输出文件的总数不超过15个，则按多路归并至少需要几趟可以完成排序？若限定这个趟数，可取的最低路数是多少？
02. 假设文件有4500个记录，在磁盘上每个块可放75个记录。计算机中用于排序的内存区可容纳450个记录。试问：
1）可以建立多少个初始归并段？每个初始归并段有多少记录？存放于多少个块中？
2）应采用几路归并？请写出归并过程及每趟需要读/写磁盘的块数。
03. 设初始归并段为(10, 15, 31), (9, 20), (22, 34, 37), (6, 15, 42), (12, 37), (84, 95)。试利用账者树进行 $m$ 路归并，手工执行选择最小的5个关键字的过程。
04. 给出12个初始归并段，其长度分别为30,44,8,6,3,20,60,18,9,62,68,85。现要做4路外归并排序，试画出表示归并过程的最佳归并树，并计算该归并树的带权路径长度WPL。
05. 【2023统考真题】对含有 $n$（$n > 0$）个记录的文件进行外部排序，采用置换-选择排序生成初始归并段时需要使用一个工作区，工作区中能保存 $m$ 个记录。请回答：
1）若文件中含有19个记录，其关键字依次是51,94,37,92,14,63,15,99,48,56,23,60,31,17,43,8,90,166,100，则当 $m = 4$ 时，可生成几个初始归并段？各是什么？
2）对任意的 $m$（$n \gg m > 0$），生成的第一个初始归并段的长度最大值和最小值分别是多少？
## 8.7.7 答案与解析
### 一、单项选择题
01. B
外部排序和内部排序最主要的区别是是否涉及内存、外存的数据交换。
<!-- page: 399 -->
第8章 椿序
387
02. C
置换选择排序得到的是长度不一定相等的归并段，选项 A 错误。外部排序的主要时间消耗在内外存之间的数据交换上，选项 B 错误。败者树是一棵完全二叉树，选项 C 正确。外部排序包括两个阶段：生成初始归并段和对初始归并段进行归并，这两个阶段都涉及对文件的读/写操作，选项 D 错误。
03. A
多路平衡归并的目的是减少归并趟数，因为当 $m$ 个初始归并段采用 $k$ 路平衡归并时，所需趟数 $s = \lceil \log_8 m \rceil$ ，若不采用多路平衡归并，则其归并趟数大于 $s$ 。
04. B
初始归并段的个数 $r = 375000 / 600 = 625$ ，因此，归并趟数 $S = \lceil \log_m r \rceil = \lceil \log_5 625 \rceil = 4$ 。第一趟把625个归并段归并成 $625 / 5 = 125$ 个；第二趟把125个归并段归并成 $125 / 5 = 25$ 个；第三趟把25个归并段归并成 $25 / 5 = 5$ 个；第四趟把5个归并段归并成 $5 / 5 = 1$ 个。
05. D
在外部排序过程中输入/输出缓冲区就是排序的内存工作区，例如进行 $m$ 路平衡归并需要 $m$ 个输入缓冲区和1个输出缓冲区，用以存放参加归并的和归并完成的记录。在产生初始归并段时也可用作内部排序的工作区。它没有传送用户界面的消息的任务。
06. C
归并趟数 $= \lceil \log_8 n \rceil$ ，其中 $k$ 表示归并的路数，$n$ 表示元素个数，当 $k = 4$ 、$n = 64$ 时，归并趟数恰好等于3，因此选取的归并路数至少是4。
07. A
置换-选择排序是外部排序中生成初始归并段的方法，用此方法得到的初始归并段的长度是不等长的，其长度平均是传统等长初始归并段的2倍，从而使得初始归并段数减少到原来的近二分之一。但是，置换-选择排序不是一种完整的生成有序文件的外部排序算法。
08. D
设内存工作区 $w = 1$ ，则文件 $\{1,2,3,4,5\}$ 产生1个有序段，而文件 $\{5,4,3,2,1\}$ 产生5个有序段，因此 $m$ 与待排文件、内存工作区大小 $w$ 和 $n$ 都有关，但不是选项A、B、C描述的直接关系。
09. C
在败者树中选取最小关键字的时间复杂度取决于败者树的高度，所需时间为 $O(\log_2 k)$ 。
10. C
说法I正确，是败者树的性质。在败者树的维护过程中，会让胜利者一直调整到根结点，说法Ⅱ正确。以小根堆为例，每次调整时，先比较下一层的两个元素（1次），找出较小值，然后比较当前元素和下一层的较小元素（1次），以决定是否向下交换位置，说法Ⅲ正确。堆在维护时，可能会在中间某层停止（若此处无须调整），而不一定要走到叶结点，说法Ⅳ错误。
11. B
最佳归并树在外部排序中的作用是设计 $m$ 路归并排序的优化方案，仿照构造哈夫曼树的方法，以初始归并段的长度为权值，构造具有最小带权路径长度的 $m$ 叉哈夫曼树，可以有效地减少归并过程中的读/写记录数，加快外部排序的速度。
12. C
$k$ 阶最佳归并树中只有度为0和 $k$ 的结点。设结点总数为 $n$ ，度为0的结点数为 $n_0$ ，度为 $k$ 的结点数为 $n_k$ ，则 $n_0 = m$ 、$n - 1 = kn_k$ ，$n = n_0 + n_k$ ，因此 $kn_k = m + n_k - 1$ ，求得 $n_k = (m - 1) / (k - 1)$ 。
13. B
题中的三叉树为使WPL最小，必须构造三叉哈夫曼树，应满足 $(n_0 - 1)\% (3 - 1) = 0$ 的条件，因
<!-- page: 400 -->
2027年数据结构考研复习指导
此需添加1个权值为0的虚叶结点，说明7个叶结点刚好可构成一棵严格的三叉树。按照哈夫曼树的原则，权为0的叶结点应离树根最远，构造三叉哈夫曼树的过程如下：
① 合并权值最小的三个结点 $0,2,3$，得到新结点的权值 $= 5$，剩下 $5,4,5,6,7$。
② 合并权值最小的三个结点 $4,5,5$，得到新结点的权值 $= 14$，剩下 $14,6,7$。
③ 合并权值最小的三个结点 $6,7,14$，得到新结点的权值 $= 27$，仅有 $27$，建树完成。
$$
\mathrm {W P L} = \sum_ {1} ^ {n} \text {权 值} W _ {\text {叶 结 点} t} \times \text {深 度} D _ {\text {叶 结 点} t} = (2 + 3) \times 3 + (4 + 5) \times 2 + (6 + 7) \times 1 = 4 6
$$
或
$$
\mathrm {W P L} = \sum_ {1} ^ {m} \text {权 值} W _ {\text {分 支 结 点} t} = 2 7 + 1 4 + 5 = 4 6
$$
每个分支结点的权值都累加了其下面所有分支结点的权值，因此采用第二种方法更方便。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
## 14. D
外部排序指的是大文件的排序，即待排序的记录存储在外存中，待排序的文件无法一次性装入内存，需要在内存和外存之间进行多次数据交换，以达到排序整个文件的目的。外部排序通常采用归并排序算法。选项A、B、C都是内部排序的方法。
## 15. B
在12路归并树中只存在度为0和度为12的结点，设度为0的结点数、度为12的结点数和要补充的结点数分别为 $n_0$、$n_{12}$ 和 $n_{\mathrm{轱}}$，则有 $n_0 = 120 + n_{\mathrm{轱}}$，$n_0 = (12 - 1)n_{12} + 1$，可得 $n_{12} = (120 - 1 + n_{\mathrm{轱}}) / (12 - 1)$。因为结点数 $n_{12}$ 为整数，所以 $n_{\mathrm{轱}}$ 是使上式整除的最小整数，求得 $n_{\mathrm{轱}} = 2$。
此外，题中为实现最佳归并，应满足12叉哈夫曼树，$n = 120$，$m = 12$，不满足 $(n - 1)\% (m - 1) = 0$ 的条件，因此需要添加两个权值为0的叶结点，使得 $n = 122$，才能满足条件。
## 16. D
利用败者树归并升序归并段，每次需要得到当前的最小关键字，因此记录“冠军”的结点保存的只能是最小关键字或最小关键字所在的归并段号。通过败者树找出最小关键字后，还需要找到该关键字所在的归并段，并移动段内元素，以继续比较下一个元素，下面分别进行讨论：①假设记录“冠军”的结点保存的是最小关键字所在的归并段号，则能直接得到最小关键字及其所在的段，时间复杂度低。②假设记录“冠军”的结点保存的是最小关键字，则查找其所在的段需要检索所有段的首元素是否与该最小关键字相等，时间复杂度高。为了提高效率，记录“冠军”的结点保存的是最小关键字所在的归并段号，而不是最小关键字。
## 二、综合应用题
## 01. 【解答】
1）设归并路数为 $m$，初始归并段个数 $r = 80$，根据归并趟数计算公式 $S = \lceil \log_m r \rceil = \lceil \log_m 80 \rceil = 3$，得 $\log_m 80 \leqslant 3$，$m^3 \geqslant 80$。由此解得 $m \geqslant 5$，即应取的归并路数至少为5。
2）设多路归并的归并路数为 $m$，需要 $m$ 个输入缓冲区和 1 个输出缓冲区。一个缓冲区对应一个文件，有 $m + 1 = 15$，因此 $m = 14$，可做 14 路归并。由 $S = \lceil \log_m r \rceil = \lceil \log_{14} 80 \rceil = 2$，即至少需要 2 趟归并可完成排序。若限定趟数为 2，由 $S = \lceil \log_m 80 \rceil = 2$，有 $80 \leqslant m^2$，可取的最低路数为 9。即要在 2 趟内完成排序，进行 9 路归并排序即可。
<!-- page: 401 -->
第8章 椿序
389
# 02. 【解答】
1）文件有 4500 个记录，用于排序的内存区可容纳 450 个记录，可建立的初始归并段有 $4500 / 450 = 10$ 个。每个初始归并段中有 450 个记录，存于 $450 / 75 = 6$ 个块中。
2）内存区可容纳 6 个块，可建立 6 个缓冲区，其中 5 个缓冲区用于输入，1 个缓冲区用于输出，因此可采用 5 路归并，归并过程如下图所示。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
共进行了 2 趟归并，每趟需要读 60 块、写 60 块。 # 03. 【解答】 进行 6 路归并排序，选择最小的 5 个关键字的败者树如下图所示。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
# 04. 【解答】 设初始归并段个数 $n = 12$，外归并路数 $k = 4$，计算 $(n - 1)\% (k - 1) = 11\% 3 = 2 \neq 0$，说明不能做完全的 4 路归并，因为多出了两个初始归并段，必须添加 $k - 2 - 1 = 1$ 个长度为 0 的空归并段，才能构成严格的 4 路归并树，即每次归并都有 $k$ 个归并段参加归并。 此时，归并树的内结点应有 $(n - 1 + 1) / (k - 1) = 12 / 3 = 4$ 个，如下图所示。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
<!-- page: 402 -->
2027年数据结构考研复习指导
$$
\mathrm{WPL} = (3 + 6 + 8) \times 3 + (9 + 18 + 20 + 30 + 44 + 60 + 62) \times 2 + (68 + 85) \times 1 = 51 + 486 + 153 = 690.
$$
## 05. 【解答】
1）当文件中的 $n$ 个记录升序排列时，只生成一个归并段，长度达到最大，为 $n$。若初始工作区内的 $m$ 个元素都大于输入文件中剩下的所有记录，则第一个归并段的长度就为 $m$，此时为第一个归并段长度最小的情况。排序过程如下表所示。
| 输出文件 FO | 工作区 WA | 输入文件 FI |
| --- | --- | --- |
| — | — | 51, 94, 37, 92, 14, 63, 15, 99, 48, 56, 23, 60, 31, 17, 43, 8, 90, 166, 100 |
| — | 51, 94, 37, 92 | 14, 63, 15, 99, 48, 56, 23, 60, 31, 17, 43, 8, 90, 166, 100 |
| 37 | 51, 94, 14, 92 | 63, 15, 99, 48, 56, 23, 60, 31, 17, 43, 8, 90, 166, 100 |
| 37, 51 | 94, 14, 92, 63 | 15, 99, 48, 56, 23, 60, 31, 17, 43, 8, 90, 166, 100 |
| 37, 51, 63 | 15, 94, 14, 92 | 99, 48, 56, 23, 60, 31, 17, 43, 8, 90, 166, 100 |
| 37, 51, 63, 92 | 15, 94, 14, 99 | 48, 56, 23, 60, 31, 17, 43, 8, 90, 166, 100 |
| 37, 51, 63, 92, 94 | 15, 14, 99, 48 | 56, 23, 60, 31, 17, 43, 8, 90, 166, 100 |
| 37, 51, 63, 92, 94, 99 | 15, 14, 56, 48 | 23, 60, 31, 17, 43, 8, 90, 166, 100 |
| 14 | 15, 23, 56, 48 | 60, 31, 17, 43, 8, 90, 166, 100 |
| 14, 15 | 60, 23, 56, 48 | 31, 17, 43, 8, 90, 166, 100 |
| 14, 15, 23 | 60, 31, 56, 48 | 17, 43, 8, 90, 166, 100 |
| 14, 15, 23, 31 | 60, 17, 56, 48 | 43, 8, 90, 166, 100 |
| 14, 15, 23, 31, 48 | 60, 17, 56, 43 | 8, 90, 166, 100 |
| 14, 15, 23, 31, 48, 56 | 60, 17, 8, 43 | 90, 166, 100 |
| 14, 15, 23, 31, 48, 56, 60 | 90, 17, 8, 43 | 166, 100 |
| 14, 15, 23, 31, 48, 56, 60, 90 | 166, 17, 8, 43 | 100 |
| 14, 15, 23, 31, 48, 56, 60, 90, 166# | 100, 17, 8, 43 | — |
| 8 | 100, 17, 43 | — |
| 8, 17 | 100, 43 | — |
| 8, 17, 43 | 100 | — |
| 8, 17, 43, 100 | — | — |
| 8, 17, 43, 100# | — | — |
生成三个初始归并段，分别是37, 51, 63, 92, 94, 99: 14, 15, 23, 31, 48, 56, 60, 90, 166: 8, 17, 43, 100。
2）最大值为 $n$，最小值为 $m$。