外部排序的败者树

外部排序的背景

当数据量太大无法全部装入内存时，需要使用外部排序。最常用的外部排序方法是多路归并排序。

基本过程

1. 生成初始归并段：将数据分成若干段，每段在内存中排序后写回外存
2. 多路归并：将 k 个归并段归并成一个有序文件

败者树的作用

在 k 路归并中，需要从 k 个归并段的当前元素中选出最小值。

• 朴素方法：比较 $k-1$ 次 → 时间太长
• 败者树：只需要 $\lceil\log_2 k\rceil$ 次比较

败者树是一棵完全二叉树，用于在 k 个元素中快速找到最小值。

败者树 vs 胜者树

• 胜者树：每个节点记录胜者（较小值的下标）
• 败者树：每个节点记录败者（较大值的下标），根节点的父节点记录最终胜者

示例一：构造 4 路归并的败者树

题目：4 个归并段的当前元素为：段1→3，段2→5，段3→2，段4→7。

叶子节点（从左到右）：段1=3，段2=5，段3=2，段4=7。

自下而上调整：

• 节点1 = 比较段1(3) 和段2(5)：败者=段2(5)，胜者=段1(3)
• 节点3 = 比较段3(2) 和段4(7)：败者=段4(7)，胜者=段3(2)
• 节点2 = 比较段1(3) 和段3(2)：败者=段1(3)，胜者=段3(2)
• 节点0 = 最终胜者 = 段3(2)

败者树：
       [0] → 段3 (最终胜者, 值=2)
       /
     [2] → 败者=段1 (值=3)
    /   \
  [1]    [3]
败者=段2  败者=段4
 (值=5)   (值=7)
 / \     / \
段1 段2  段3 段4
 3   5   2   7

示例二：调整败者树

题目：接上例，输出段3的元素 2 后，段3读入下一个元素 8，调整败者树。

1. 段3的值从 2 变为 8
2. 从叶子节点（段3）出发向上，父节点是 3，败者是段4(7)
3. 比较段3(8) 和段4(7)：败者=段3(8)，胜者=段4(7)
4. 节点3更新为段3（败者）
5. 继续向上到节点2，败者是段1(3)
6. 比较段4(7) 和段1(3)：败者=段4(7)，胜者=段1(3)
7. 节点2更新为段4（败者）
8. 最终胜者=段1(3)

输出：3（来自段1）。比较次数：2 次 $= \log_2 4 = 2$。

示例三：k 路归并的比较次数

题目：8 路归并，用败者树选出一个最小元素需要多少次比较？

答：$\lceil\log_2 8\rceil =$ 3 次，而朴素方法需要 7 次（$8-1$）。