21天学习挑战赛-多路平衡归并的实现

​
​

活动地址：CSDN21天学习挑战赛

学习的最大理由是想摆脱平庸，早一天就多一份人生的精彩；迟一天就多一天平庸的困扰。各位小伙伴，如果您：
想系统/深入学习某技术知识点…
一个人摸索学习很难坚持，想组团高效学习…
想写博客但无从下手，急需写作干货注入能量…
热爱写作，愿意让自己成为更好的人…
…

多路平衡归并的实现

1. 矛盾的解决

从式(11-2)得知, 增加 $k$ 可以减少 $s$, 从而减少外存读/写的次数。但是, 从下面的讨论中又可发现，单纯增加 $k$ 将导致增加内部归并的时间 $u{t}_{mg}$。那么，如何解决这个矛盾呢？

1. 先看 2-路归并。令 $u$ 个记录分布在两个归并段上，按 merge 过程进行归并。每得到归并后的一个记录，仅需一次比较即可，则得到含 $u$ 个记录的归并段需进行 $u-1$ 次比较。

2. 再看 k-路归并。令 $u$ 个记录分布在 $k$ 个归并段上，显然，归并后的第一个记录应是 $k$ 个归并段中关键字最小的记录，即应从每个归并段的第一个记录的相互比较中选出最小者，这需要进行 $k-1$ 次比较。同理，每得到归并后的有序段中的一个记录，都要进行 $k-1$ 次比较。显然，为得到含 $u$ 个记录的归并段需进行 $(u-1)(k-1)$ 次比较。由此，对 $n$ 个记录的文件进行外排时，在内部归并过程中进行的总的比较次数为 $s(k-1)(n-1)$。假设所得初始归并段为 $m$ 个，则由式 $(11-2)$ 可得内部归并过程中进行比较的总的次数为

⌊ log ⁡ k m ⌋ ( k − 1 ) ( n − 1 ) t m g = ⌊ log ⁡ 2 m log ⁡ 2 k ⌋ ( k − 1 ) ( n − 1 ) t m g ( 11 − 3 ) \qquad⌊logkm⌋(k−1)(n−1)tmg=⌊log2mlog2k⌋(k−1)(n−1)tmg(11−3)

⌊logk​m⌋(k−1)(n−1)tmg​=⌊log2​klog2​m​⌋(k−1)(n−1)tmg​(11−3)​

由于 $\frac{k-1}{lo{g}_{2}k}$ 随 $k$ 的增长而增长，则内部归井时间亦随 $k$ 的増长而增长，这将抵消由于増大 $k$ 而减少外存信息读写时间所得效益，这是我们所不希望的。然而，若在进行 k - 路归并时利用 “败者树”（Tree of Loser），则可使在 $k$ 个记录中选出关键字最小的记录时仅需进行 $\lfloor lo{g}_{2}k\rfloor$ 次比较，从而使总的归并时间由式 $(11-3)$ 变为 $\lfloor {\log }_{2}m\rfloor (n-1)t_{mg}$，显然，这个式子和 $k$ 无关，它不再随 $k$ 的增长而增长。

败者树

那么，什么是“败者树”？它是树形选择排序的一种变型。“胜者树”，因为每个非终端结点均表示其左、右孩子结点中的“胜者”。反之，若在双亲结点中记下刚进行完的这场比赛中的败者，而让胜者去参加更高层的比赛，便可得到一棵“败者树”。

败者树的初始化也容易实现，只要先令所有的非终端结点指向一个含最小关键字的叶子结点，然后从各个叶子结点出发调整非终端结点为新的败者即可。

2. 代码实例

下面的算法 11.1 简单描述利用败者树进行 k-路 归并的过程。为了突出如何利用败者树进行归并，在算法中避开了外存信息存取的细节，可以认为归并段已在内存。算法 11.2 描述在从败者树选得最小关键字的记录之后，如何从叶到根调整败者树选得下一个最小关键字。算法 11.3 为初建败者树的过程的算法描述。

算法 11.1

typedef int LoserTree[k];                       //败者树是完全二叉树且不含叶子，可采用顺序存储结构 

typedef struct{
    KeyType key;
}ExNode, External[k + 1];                       //外结点，只存放待归并记录的关键字

void K_Merge(LoserTree & ls, External & b){

    //利用败者树 ls 将编号从 0 到 k - 1 的 k 个输入归并段中的记录归并到输出归并段。
    //b[0] 至 b[k - 1] 为败者树上的 k 个叶子结点，分别存放 k 个输入归并段中当前记录的关键字。
    for(i = 0; i < k; ++ i) 
        input(b[i].key);                        //分别从 k 个输入归并段读入该段当前，第一个记录的关键字到外结点

    CreateLoserTree(ls);                        //建败者树 ls, 选得最小关键字为 b[ls[0]].key

    while(b[ls[0]].key != MAXKEY){
        q = ls[0];                              //q 指示当前最小关键字所在归并段
        output(q);                              //将编号为 q 的归并段中当前（关键字为 b[q].key）的记录，写至输出归并段

        input(b[q].key,q);                      //从编号为 q 的输入归并段中读入下一个记录的关键字
        adjust(ls, q);                          //调整败者树，选择新的最小关键字 
    }// while 

    output(ls[0]);                              //将含最大关键字 MXXEY 的记录写至输出归并段 

}//K_Merge
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

算法 11.2

void Adjust(LoserTree & ls, int s){

    //沿从叶子结点 b[s] 到根结点 ls[0] 的路径调整败者树
    t = (s + k) / 2;                            //ls[t] 是 b[s] 的双亲结点 
    
    while (t > 0){
        if (b[s].key > b[ls[t]].key) 
            s <--> ls[t];                       //s 指示新的胜者
    }

    1s[0] = s;

}// Adjust
1
2
3
4
5
6
7
8
9
10
11
12
13

算法 11.3

void CreateLoserTree (Losertree &1s){

    //已知 b[0] 到 b[k - 1] 为完全二叉树 ls 的叶子结点存有 k 个关键字，沿从叶子到根的 k 条路径将 ls 调整成为败者树。
    
    b[k].key = MINKEY;                          //设 MINKEY 为关键字可能的最小值 
    
    for(i = 0; i < k; ++i) 
        ls[i] = k;                              //设置 ls 中“败者”的初值

    for(i = k - 1; i>= 0; --i) 
        Adjust(ls, i);                          //依次从 b[k - 1], b[k - 2],...,b[0] 出发调整败者

}// CreateLoserTree
1
2
3
4
5
6
7
8
9
10
11
12
13

最后要提及一点，$k$ 值的选择并非越大越好，如何选择合适的 $k$ 是一个需要综合考虑的问题。