【算法概论】k路归并
首先了解两个概念，胜者树和败者树：
胜者树和败者树都是二叉排序树，是树形选择排序的一种变形。每个叶子节点相当于一位选手，每个中间结点相当于一场比赛，每一层相当于一轮比赛。胜者树的中间结点记录的是胜者的标号，败者树的中间结点记录败者的标号。因此，胜者树和败者树的根节点，就是最终的胜者或败者 —— 反映到一组数据中，可以是最大值或最小值。
胜者树与败者树可以在log(n)的时间内找到最值。任何一个叶子结点的值改变后，利用中间结点的信息，还是能够快速地找到最值。在k路归并排序中经常用到。
胜者树：
规定数小者胜。
b3 PK b4，b3胜b4负，内部结点ls[4]的值为3；
b3 PK b0，b3胜b0负，内部结点ls[2]的值为3；
b1 PK b2，b1胜b2负，内部结点ls[3]的值为1；
b3 PK b1，b3胜b1负，内部结点ls[1]的值为3。
如果我们将b3的值改为11，就需要对该胜者树进行重构，重构后的胜者树如下所示：
b3 PK b4，b3胜b4负，内部结点ls[4]的值为3；
b3 PK b0，b0胜b3负，内部结点ls[2]的值为0；
b1 PK b2，b1胜b2负，内部结点ls[3]的值为1；
b0 PK b1，b1胜b0负，内部结点ls[1]的值为1。
由上面的例子，可以很容易的理解：
胜者树的一个优点是，如果一个选手的值改变了，只需要沿着从该结点到根结点的路径修改这棵二叉树，而不必改变其他比赛的结果。
败者树：
败者树是胜者树的一种变体。在败者树中，用父结点记录其左右子结点进行比赛的败者，而让胜者参加下一轮的比赛。败者树的根结点记录的是败者，因此需要加一个结点来记录整个比赛的胜利者。
规定数大者败。
b3 PK b4，b3胜b4负，将败者的标号赋给父结点，内部结点ls[4]的值为4；
b3 PK b0，b3胜b0负，内部结点ls[2]的值为0；
b1 PK b2，b1胜b2负，内部结点ls[3]的值为2；
b3 PK b1，b3胜b1负，内部结点ls[1]的值为1；
在根结点ls[1]上又加了一个结点ls[0]=3，记录的最后的胜者。
如果我们把b3的值改为13，重构后的图如下所示：
将新进入选择树的结点与其父结点进行比赛：将败者存放在父结点中；而胜者再与父结点的父结点（即它爷爷）进行比较；
比赛沿着到根结点的路径不断进行，直到ls[1]处。把败者存放在结点ls[1]中，胜者存放在ls[0]中。
败者树的重构只是与该结点的父结点的记录有关，而胜者树的重构还与该结点的兄弟结点有关。
好了，接下来我们看k路归并的问题。
k路归并一般都用在外排序上，是为了减少访问磁盘的次数。那么，基于两路归并的有什么缺点呢，我们可以参照下图看一看：
假设初始化归并段有m个，则二路归并需要访问硬盘的次数为。按照这个方法，我们只要增加k就可以减少次数。就是说是k路归并的话，访问硬盘次数就是
。但是这里边存在一个矛盾：如果增大k，归并的时候比较次数增加了。那我们只要找到一种可以增大k，然后比较次数又比较少的方法就行了，这就是多路归并-败者树。看下面推导：
败者树编程（k路归并）
在实现败者树编程中，我们把败者树的叶子节点和非叶子结点分开定义：
(1)k路归并，k为需要归并的数组个数；
(2)叶子结点存放在b数组中：b[0]、b[1]、b[2]、……、b[k]，最后一个叶子节点即b[k]，存放一个比所有记录结点都小的值，我们可以记为INT_MIN；
(3)非叶子结点定义为ls[k]、ls[k-1]、ls[k-2]、……ls[1]，存放各次比较的败者索引，ls[0]存放最后的冠军。
定义完成啦，然后我们就开始编程：
1、败者树的创建：
#include <iostream>
using namespace std;
#define K 5 //表示5路归并
#define MIN INT_MIN
void Adjust(int s);
void CreateLoser();
int b[K + 1] = { 17, 5, 10, 39, 15 }; //叶子结点的值
int ls[K] = { 0 };//记录败者的序号
int main()
{
CreateLoser();
system("pause");
return 0;
}
/******
调整败者树
s为待调整的结点在b数组中的索引
******/
void Adjust(int s)
{
for (int t = (s + K) / 2; t > 0; t = t / 2)
{
if (b[s] > b[ls[t]]) //如果待调整结点大于父结点指向的元素值，说明目前的b[s]值为败者
{
int temp = s;
s = ls[t]; //s永远是指向这一轮比赛最小节点 —— 胜者
ls[t] = temp; //将败者的索引 —— s赋给父结点
}
}
ls[0] = s; //将最小节点的索引存储在ls[0]
return;
}
/*****
创建一个败者树
*****/
void CreateLoser()
{
b[K] = MIN; //b[K]存放一个比所有记录都小的值，作为虚结点
//将ls[0...k-1] = K，表示第K+1（虚设）个归并段的记录当前最小
for (int i = 0; i < K; ++i)
{
ls[i] = K;
}
//从k-1到0，每次加入一个记录进行一次调整，算法自顶向下，直到所有记录加进来
for (int i = K - 1; i >= 0; --i)
{
Adjust(i); //加入一个基点，要进行调整
}
return;
}创建树的过程如下图所示：
2、归并排序：
读入数据，创建归并树，判断b[ls[0]] == MAX，等于表示所有记录都已输出。不等于，输出当前冠军，然后从相应归并段读入数据填上。注意，如果相应的归并段已经空了，则填上MAX。下面给出伪代码：
void K_Merge()
{
for (int i = 0; i < K; ++i)
{
input(i); //伪代码，输入到b[i]
}
CreateLoser();
while (b[ls[0]] != MAX)
{
//只要不是最大值
int q = ls[0]; //得到冠军的索引
output(b[q]); //伪代码
input(b[q]); //伪代码
Adjust(q);
}
}3、整篇代码：
首先将k个归并段中的首元素关键字依次存入External[0] ~ External[k-1]的叶子结点空间里，然后调用CreateLoserTree创建败者树，创建完毕之后最小的关键字下标（即所在归并段的序号）便被存入LoserTree[0]中。然后不断循环：把LoserTree[0]所存最小关键字来自于哪个归并段的序号记为p，将该归并段的首元素输出到有序归并段里，然后把下一个元素关键字放入上一个元素本来所在的叶子结点External[p]中，调用Adjust函数顺着External[p]这个叶子结点往上调整败者树，直到新的最小的关键字被选出来，其下标同样存在LoserTree[0]中。循环这个操作过程直至所有元素被写到有序归并段里。
/*
设计和实现一个有效的分治算法解决 k-路合并操作 问题，并分析时间复杂度。
*/
#include <iostream>
#include <fstream>
using namespace std;
#define LEN 10 //最大归并段长
#define MINKEY -1 //默认全为正数
#define MAXKEY 100 //最大值,当一个段全部输出后的赋值
void K_Merge();
void Adjust(int s);
void CreateLoserTree();
struct Array
{
int arr[LEN];
int num; //每个数组的长度
int pos;
}*A;
int k; //k路归并
int cnt; //所有数组的长度和
int *LoserTree, *External;
int main()
{
ifstream in("in.txt");
cnt = 0;
in >> k; //读取数组的个数
A = (Array *)malloc(sizeof(Array)*k); //开辟k个数组的空间
for (int i = 0; i < k; i++)
{
in >> A[i].num; //读取每一个数组的长度
cnt = cnt + A[i].num; //cnt为所有数组的长度和
for (int j = 0; j < A[i].num; j++)
{
in >> A[i].arr[j]; //读取每个数组中的元素
}
A[i].pos = 0; //每次将所有数组的第pos个元素提取出来，创建败者树，先提取第0个元素，因此pos初始值为0
}
LoserTree = (int *)malloc(sizeof(int) * k); //为败者树的非叶子结点开辟k个int空间
External = (int *)malloc(sizeof(int) * (k + 1)); //为败者树的叶子节点开辟k+1个int空间
K_Merge(); //k路归并
return 0;
}
/******
调整败者树
s为待调整的结点在b数组中的索引
******/
void Adjust(int s)
{
int t = (s + k) / 2;
int temp;
while (t > 0)
{
if (External[s] > External[LoserTree[t]]) //如果待调整结点大于父结点指向的元素值，说明目前的External[s]值为败者
{
temp = s;
s = LoserTree[t]; //s永远是指向这一轮比赛最小节点 —— 胜者
LoserTree[t] = temp; //将败者的索引 —— s赋给父结点
}
t = t / 2;
}
LoserTree[0] = s; //将最小节点的索引存储在败者树的最顶端
}
/*****
创建败者树
*****/
void CreateLoserTree()
{
External[k] = MINKEY;
for (int i = 0; i < k; ++i)
{
LoserTree[i] = k;
}
//从最底层调整败者树
for (int i = k - 1; i >= 0; --i)
{
Adjust(i);
}
return;
}
/*****
k路归并
*****/
void K_Merge()
{
int p;
//给External数组赋值，分别为A[0、1、…… k].arr[i]
for (int i = 0; i < k; i++)
{
p = A[i].pos;
External[i] = A[i].arr[p]; //每次将所有数组的第pos个元素提取出来，创建败者树
A[i].pos++;
}
//创建败者树
CreateLoserTree();
int n = 0;
while (n < cnt)
{
p = LoserTree[0];
cout << External[p] << ", "; //输出败者树最顶端存储的索引在External数组中对应的元素，即最小值
n += 1;
if (A[p].pos >= A[p].num) //如果第p个数组中的数据均已进入有序归并段，将External[p]赋值为MAXKEY
{
External[p] = MAXKEY;
}
else
{
External[p] = A[p].arr[A[p].pos];
A[p].pos++;
}
Adjust(p);
}
cout << endl;
return;
}文件中的数据为：
运行结果：