k路合并 - (sunznx) 振翅飞翔
11 October 2019

k 路合并:将 k 个已经排好序的数组,合并成 1 个排好序的数组

假设我们要合并的是两个数组,即 k 为 2,可以用如下伪代码实现:

i = 0
j = 0

len1 = arr1->size
len2 = arr2->size

sortedArr = []
idx = 0
while (i != len1 || j != len2) {
  if (i == len1) {
    sortedArr[idx++] = arr2[j++]
  } else if (j == len2) {
    sortedArr[idx++] = arr1[i++]
  } else {
    if (arr1[i] <= arr2[j]) {
      sortedArr[idx++] = arr1[i++]
    } else {
      sortedArr[idx++] = arr2[j++]
    }
  }
}

当我们 k 比较大的时候,我们用一个堆 heap 来实现。使用堆的原因是,当你插入一个新元素的时候,堆可以在 O(logN) 的时间内重新维护堆的最值。

假设我们往 heap 里面放 k 个数, heap[0] 即为这 k 个数的最小值,便可以把这个值放到 sortedArr 中,继续将从原来的数组里面取数据,放进堆

在实现的时候,我们可以先往 heap 里面放 k 个 minValue 去填充堆,当排序到某个数组没数据了,我们可以继续往 heap 里面放一个 maxValue。具体的代码可以参考 这里

胜者树和败者树

k 路合并常常会涉及到另外两个主题:胜者树和败者树

用堆来合并数组有一个缺点:每次 modifyTop 的时候,都要和左右两个子节点进行比较,每次比较的次数是 2 次,总时间是 O(2logn)

胜者树

胜者树是维护另外一种数据结构,这个结构具有堆的特性,但不再是一个堆。胜者树分为 “叶子节点” 和 “非叶子节点”。叶子节点存的是数据,非叶子节点存的是他的左右两个子节点的 “胜者” 的 下标

“叶子节点” 和 “非叶子节点” 的个数有一个关系:非叶子节点 + 1 = 叶子节点个数。

胜者树每次 modifyTop 的时候,从 “叶子节点” 开始往上更新 “胜者” 的下标存储到 “非叶子节点”,每次比较的次数是 1 次,总时间是 O(log2n) ,是一种空间换时间的方法(实际上也不会快很多)

败者树

胜者树在进行比较的时候是和 “兄弟节点” 进行比较的,虽然每次比较次数是 1 次,但是获取当前的节点的兄弟节点是很麻烦的。需要获取父节点,然后再通过父节点的左右 “子节点” 来进行比较。
假如我们在 parent 节点里面,不仅存储了 “胜者” 的下标,还存储了 “败者” 的下标,那么在自底向上进行比较的时候,我们只需要将当前的 “胜者” 和父节点的 “败者” 进行比较。父节点的 “败者” 存的就是当前节点的兄弟节点

可以通过如下两部分代码获得一些灵感: 胜者树败者树

题外话

经过测试,胜者树和败者树对于 k 路归并的优化实际上不是很大,但是这个技巧有点意思