多路归并与胜者树败者树

多路归并从 O(nk) 到 O(nlogn) 的优化切入点为在每次寻找最值上。我们可以利用堆、胜者树败者树这种每次调整堆拿到最值，只需要 O(logn) 复杂度的结构，这样我们就把多路归并的问题转嫁到了取最值的问题。（这里使用最小值举例）

堆

N 个数求最值，可以使用大根堆或者小根堆来实现，使用堆排序的核心子程序，在构建堆完毕之后，取根，使用下一个数替换，并重新调整堆，得出下一个最值，并反复之。
注意
与堆排序不同的是，我们在提取出 k 路的第一个元素组成新的待筛选数据集合之后，应当使用一个新的等长的辅助数组来记录对应数据集的下标，因为带筛选数据集合代表着 k 路之间的相对顺序。我们需要使用辅助数组来进行建堆，这样辅助数组中的第一个元素的值即是最值，然后将对应下标的数据集的值换为对应 k 路的下一个值，并开始对新的根进行筛选调整堆即可。

/**
 * 对 index 所在的节点进行堆调整
 *（建堆的时候是一度和二度节点，取根后调整堆的时候则是根节点）
 **/
function minHeapify(arr, index, heapSize, dataArr) {
  let iMin = index, iLeft = 2 * index + 1, 2 * (index + 1)
  if(iLeft < heapSize && dataArr[arr[index]] > dataArr[arr[iLeft]]) {
    iMin = iLeft
  }
  
  if(iRight < heapSize && dataArr[arr[iMin]] > dataArr[arr[iRight]]) {
    iMin = iRight
  }

  if(iMin !== index) {
    swap(arr, iMax, index)
    minHeapify(arr, iMax, heapSize, dataArr)
  }
}

/**
 *  将初始的无序数组调整为小根堆
 **/
function buildMinHeap(arr, heapSize, dataArr) {
  let iParent = Math.floor((heapSize - 1) / 2)
  for(let i = iParent; i >= 0; i--) {
    minHeapify(arr, i, heapSize, dataArr)
  }
}

/**
 * @ways 二维数组，存放多路数据
 **/
const MAX = 10000
function multiWayMerge (ways) {
  const dataArr = ways.map((item, index) => ({value: item[0], index: 0})) // 通过记录 index 来追溯同路中前后两个节点
  , heapArr = dataArr.map((item, index) => index)
  , res = []
  , leftWaysCount = ways.length
  buildMinHeap(heapArr, heapArr.length，dataArr)

  const { value, index } = dataArr[heapArr[0]]
  while (leftWaysCount > 1) {
    res.push(dataArr[heapArr[0]].value)
    if (ways[heapArr[0]][index + 1]) {
      dataArr[heapArr[0]] = {
        value: ways[heapArr[0]][++index]
        index
      }
    } else {
      dataArr[heapArr[0]] = {value: MAX}
      leftWaysCount --
    }
    minHeapify(heapArr, 0, heapArr.length, dataArr)
  }
  return res.concat(ways[heapArr[0]].slice(index))
}

在调整堆的时候，只需要将比较对象换成数据集里的数据即可。

败者树

何为败者树？

首先使用一个和数据集等长大小的树，其中 0 用来存储冠军，其他节点用来存储失败者。大概流程是将叶子结点和父节点去秋名山 PK，失败者留下车标（下标），胜利者继续向上 PK。每一个节点统统比较一次，来初始化树。

/**
 * 调整败者树
 * @winner 数据叶子中冠军的位置, 每次冠军被该路中的新数据置换掉之后，需要更新败者树，从而得出心得优胜者
 **/
function adjustLt (tree, dataArr, winner) {
  let parent = Math.floor((tree.length + winner) / 2)
  while (parent > 0) {
    if (tree[winner] > tree[tree[parent]]) { // winner 失败了
      let tmp = tree[parent]
      tree[parent] = winner
      winner = tmp
    }
    parent = Math.floor(parent / 2)
  }
  tree[0] = winner
}

/**
 * tree 长度为 dataArr 的长度，为 m
 **/
function buildLt (tree, dataArr) {
  tree = dataArr.map((item, index) => index)
  dataArr.map((item, index) => {
    adjustLt(tree, dataArr, index)
  })
}

function multiWayMerge (ways) {
   const dataArr = ways.map((item, index) => ({value: item[0], index: 0})) // 通过记录 index 来追溯同路中前后两个节点
    , tree = []
    , res = []
    , leftWaysCount = ways.length
  buildLt(tree, dataArr)

  const { value, index } = dataArr[tree[0]]
  while (leftWaysCount > 1) {
    res.push(value)
    if (ways[tree[0]][++index]) {
      dataArr[tree[0]] = {
        value: ways[tree[0]][index]
        index
      }
    } else {
      dataArr[tree[0]] = {value: MAX}
      leftWaysCount --
    }
    adjustLt(tree, dataArr, tree[0])
  }
  return res.concat(ways[tree[0]].slice(index))
}

胜者树

何为胜者树？

将数据集合作为叶子结点构建一颗完全二叉树，将叶子的值两两比较，优胜者记录于父节点中，依次往上，最终的胜出者即为最值。

在叶子结点发生变动之后，怎么重新调整呢？

类似于堆的筛选，我们只需要按照同样的策略，在新的叶子结点的位置一步步更新左或者右子树的一个分支，因为不论是胜者树还是败者树，叶子的更改不会影响到其他无关小组赛的结果。（用通俗的话讲，冠军的替补上场后，替补不论在初赛中赢还是输，新晋者都会对树的某分支产生印象，这里的影响有两种：替补依旧是冠军，替补不是冠军，有新的晋级者）

function adjustWt (tree, winner) {
  while (true) {
    let parent = Math.floor(winner / 2)
    let brother = winner % 2 ? winner + 1 : winner - 1
    tree[parent] = tree[brother].value > tree[winner].value ? tree[winner] : tree[brother]
    if(parent === 0) {
      break
    }
    winner = parent
  }
}

/**
 * tree 的大小为 dataArr 长度 - 1
 */
function buildWt (tree, dataArr) {
  const treeSize = dataArr.length - 1
  dataArr = dataArr.map((value, index) => ({value, index}))
  for(let i = treeSize - 2; i >= 0 i--) { 
    let leftChild = 2 * i + 1, rightChild = 2 * (i + 1)
    let leftNode = leftChild > treeSize - 1 ? dataArr[leftChild - treeSize] : tree[leftChild]
    let rightNode = rightChild > treeSize - 1 ? dataArr[rightChild - treeSize] : tree[rightChild]
    tree[i] = leftNode.value > rightNode.value ? {...rightNode} : {...leftNode}
  }
  tree.push(...dataArr)
}

堆

败者树

何为败者树？

胜者树

何为胜者树？

在叶子结点发生变动之后，怎么重新调整呢？

内容目录