外部排序：多路归并树

定义：

1、按可用内存大小，将外存上的记录文件分成若干个归并段 (segments)

2、依次读入内存并利用有效的外部排序方法进行排序

3、将排序后的有序子文件写入外存

实现：

利用败者树进行k路归并，使得每次归并在k个记录中选出最小记录仅需进行次（二叉树的深度）比较，从而使总的归并时间为。其中，m为初始归并段个数，n为总记录数，每次比较时间。

败者树：

典型的4路败者树如下图：

----------à

直观的，败者树是一棵完全二叉树，可由数组保持。其中根节点保存一次比较中的冠军；叶节点保存4个归并段的输入流；非叶结点保存一次比较中的败者。

难点1：一轮比较选出最小关键记录并调整败者树

调整的发起点：值发生变化的叶节点，必然使对应的父节点发生变化。注意，父节点中记录的败者必然是另一棵子树的胜者，但是败给了本子树的胜者，如。

调整：

1、i保存前一次比较的胜者，与的败者比较

If i失败: ，发生互换

2、如此递归的向根节点调用，直到根节点，将i中的冠军计入

难点2：败者树的初始化

1、将非叶结点初始化为可能的最小值（冠军）

2、由至调整败者树

注意点：

每个归并段内的数据是有序的，这与归并排序是一致的。并且归并段的最后需要一个全局最小的"哨兵"，防止归并段读空（仔细想想），并且当冠军为"哨兵"时，程序退出。

思想：以空间保存历次比较结果，将一般k-路归并选择一次最小值的k-1次操作变为，典型的时空互换思想。

代码：

import java.io.*;
public class LoserTree {
public static void main(String[] args) {
PrintWriter[] data = new PrintWriter[LoserTree.K];
BufferedReader[] segments = new BufferedReader[LoserTree.K];
try {
for (int i = 0; i < LoserTree.K; i++) {
data[i] = new PrintWriter(new FileWriter(i + ".txt"));
}
for (int k = 0; k < 5; k++) {
for (int i = 0; i < 5; i++) {
data[k].println(21 - 5 * k + i);
}
data[k].println(LoserTree.MAXKEY);
}
for (int i = 0; i < LoserTree.K; i++) {
data[i].close();
}
for (int i = 0; i < LoserTree.K; i++) {
segments[i] = new BufferedReader(new FileReader(i + ".txt"));
}
LoserTree Sorter = new LoserTree();
Sorter.merge(segments);
for (int i = 0; i < LoserTree.K; i++) {
segments[i].close();
}
} catch (Exception e) {
e.printStackTrace();
}
}
static final int K = 5;
static final int MINKEY = -100;
static final int MAXKEY = 100;
public int[] LS = new int[K];
public int[] b = new int[K + 1];
PrintWriter result;
public void merge(BufferedReader[] in) {
try {
result = new PrintWriter(new File("result.txt"));
for (int i = 0; i < K; i++) {
input(in[i], i);
}
create();
int q;
while (b[LS[0]] != MAXKEY) {
q = LS[0];
output(q);
input(in[q], q);
adjust(q);
}
result.close();
} catch (Exception e) {
// TODO Auto-generated catch block
throw new RuntimeException(e);
}
}
private void create() {
b[K] = MINKEY;
for (int i = 0; i < K; i++) {
LS[i] = K;
}
for (int i = K-1; i > -1; i--) {
adjust(i);
}
}
private void adjust(int i) {
int parent = (i + K) / 2;
int temp;
while (parent > 0) {
if (b[i] > b[LS[parent]]) {
temp = LS[parent];
LS[parent] = i;
i = temp;
}
parent = parent / 2;
}
LS[0] = i;
}
private void input(BufferedReader in, int i) {
try {
b[i] = Integer.valueOf(in.readLine());
} catch (Exception e) {
// TODO Auto-generated catch block
throw new RuntimeException(e);
}
}
private void output(int i) {
result.println(b[i]);
result.flush();
}
}