多路平衡归并算法（基于败者树归并有序段）（归并中的归并）

http://data.biancheng.net/view/77.html

---

如果毫无限度地增加 k 值，虽然会减少读写外存数据的次数，但会增加内部归并的时间（每次需要的读取/计算时间上升），得不偿失。

为了避免在增加 k 值的过程中影响内部归并的效率，在进行 k-路归并时可以使用“败者树来实现，该方法在增加 k 值时不会影响其内部归并的效率。

• 从效率上讲：使用败者树之前的k-路归并复杂度大约是
  使用败者树后的复杂度大约是，n是单个段的长度，k是归并段的个数。

步骤：

1）：首先将k个归并段中的首元素关键字依次存入b[0]--b[k-1]的叶子结点空间里，然后调用CreateLoserTree创建败者树，创建完毕之后最小的关键字下标（即所在归并段的序号）便被存入ls[0]中。然后不断循环：

2）把ls[0]所存最小关键字来自于哪个归并段的序号得到为q，将该归并段的首元素输出到有序归并段里，然后把下一个元素关键字放入上一个元素本来所 在的叶子结点b[q]中，调用Adjust顺着b[q]这个叶子结点往上调整败者树直到新的最小的关键字被选出来，其下标同样存在ls[0]中。循环这个 操作过程直至所有元素被写到有序归并段里。

image.png image.png

#include <stdio.h>
#define k 5
#define MAXKEY 10000
#define MINKEY -1
typedef int LoserTree[k];//表示非终端结点，由于是完全二叉树，所以可以使用一维数组来表示
typedef struct {
    int key;
}ExNode,External[k+1];
External b;//表示败者树的叶子结点
//a0-a4为5个初始归并段
int a0[]={10,15,16};
int a1[]={9,18,20};
int a2[]={20,22,40};
int a3[]={6,15,25};
int a4[]={12,37,48};
//t0-t4用于模拟从初始归并段中读入记录时使用
int t0=0,t1=0,t2=0,t3=0,t4=0;
//沿从叶子结点b[s]到根结点ls[0]的路径调整败者树
void Adjust(LoserTree ls,int s){
    int t=(s+k)/2;
    while (t>0) {
        //判断每一个叶子结点同其双亲结点中记录的败者的值相比较，调整败者的值，其中 s 一直表示的都是胜者
        if (b[s].key>b[ls[t]].key) {
            int swap=s;
            s=ls[t];
            ls[t]=swap;
        }
        t=t/2;
    }
    //最终将胜者的值赋给 ls[0]
    ls[0]=s;
}
//创建败者树
void CreateLoserTree(LoserTree ls){
    b[k].key=MINKEY;
    //设置ls数组中败者的初始值
    for (int i=0; i<k; i++) {
        ls[i]=k;
    }
    //对于每一个叶子结点，调整败者树中非终端结点中记录败者的值
    for (int i=k-1; i>=0; i--) {
        Adjust(ls, i);
    }
}
//模拟从外存向内存读入初始归并段中的每一小部分
void input(int i){
    switch (i) {
        case 0:
            if (t0<3) {
                b[i].key=a0[t0];
                t0++;
            }else{
                b[i].key=MAXKEY;
            }
            break;
        case 1:
            if (t1<3) {
                b[i].key=a1[t1];
                t1++;
            }else{
                b[i].key=MAXKEY;
            }
            break;
        case 2:
            if (t2<3) {
                b[i].key=a2[t2];
                t2++;
            }else{
                b[i].key=MAXKEY;
            }
            break;
        case 3:
            if (t3<3) {
                b[i].key=a3[t3];
                t3++;
            }else{
                b[i].key=MAXKEY;
            }
            break;
        case 4:
            if (t4<3) {
                b[i].key=a4[t4];
                t4++;
            }else{
                b[i].key=MAXKEY;
            }
            break;
        default:
            break;
    }
}
//败者树的建立及内部归并
void K_Merge(LoserTree ls){
    //模拟从外存中的5个初始归并段中向内存调取数据
    for (int i=0; i<=k; i++) {
        input(i);
    }
    //创建败者树
    CreateLoserTree(ls);
    //最终的胜者存储在 is[0]中，当其值为 MAXKEY时，证明5个临时文件归并结束
    while (b[ls[0]].key!=MAXKEY) {
        //输出过程模拟向外存写的操作
        printf("%d ",b[ls[0]].key);
        //继续读入后续的记录
        input(ls[0]);
        //根据新读入的记录的关键字的值，重新调整败者树，找出最终的胜者
        Adjust(ls,ls[0]);
    }
}
int main(int argc, const char * argv[]) {
    LoserTree ls;
    K_Merge(ls);
    return 0;
}