多路平衡归并
定义
def
k 路平衡归并的定义要求如下：
- 最多只能有 k 的段归并为 1 个；
- 每一个趟归并中，若有 m 个归并段参与归并，则经过这一趟处理得到
个新的归并段；
例如，下图就是一个合格的 4 路平衡归并。
而，下图就是不合法的：
性质
多路归并的流程
假设有 k 个序列需要我们合并，与二路归并同理，我们需要对这 k 个序列的第一个元素所构成的新序列中找到最小值。找到最小值，我们将弹出这个元素，然后继续寻找最小值。而败者树就是适应这个过程的数据结构。
IO 次数就是 WPL
于是，我们可以就使用最佳归并树找到最小的 WPL，从而最小化磁盘 IO 次数。