【数据结构】败者树的建树与比较过程

前置知识

归并段

• 外部排序算法通常用于处理大规模数据，其中数据量远超过计算机内存的容量。由于内存无法一次性容纳全部数据，因此需要将数据划分为较小的片段进行排序，在排序过程中将这些片段合并成一个有序的序列
• 这些归并段内部是有序的，各个归并段之间无序
• 如图，有 3 个归并段，内部升序
  

建树过程

• 假设有 5 个节点，给这些节点编号
  

• 17 是 0 号节点，5 是 1 号节点，…，15 是 4 号节点

• 为每个节点创建一个根节点，根节点的值是其编号，叶子节点是值
  

• 从子树中任意挑选两个子树的根节点进行比较，比较对应的值，假设比较规则是：值小的胜出
  本例中，初始有 5 棵子树

• 比较顺序是任意的，假设根节点为 0 和 1 对应子树进行比较，取出根节点对应的值，5 < 17，5 胜出

  • 除去两棵子树的根节点后，胜者的根节点作为两棵子树的爷节点，败者的根节点作为两棵子树的父节点
  • 即 0 作为父节点，1 作为爷节点

  

• 比较根节点为 3 和 4 对应子树，取出根节点对应的值，15 < 29，15 胜出
  3 作为父节点，4 作为爷节点
  

• 比较根节点为 1 和 2 对应的子树，5 < 10，5 胜出
  1 作为爷节点，2 作为父节点
  

• 比较根节点为 1 和 4 对应的子树，5 < 15，5 胜出
  1 作为爷节点，4 作为 父节点
  

• 可以看出，根节点是 1，其对应的值是 5，也就是{17, 5, 10, 29, 15} 中的最小值，共比较 4 次
  败者树构建完成

比较过程

• 将根节点对应的值进行输出，假设编号 1 所在的归并段还有元素需要比较，是 44

• 败者树需要调整，将根节点重新和编号 1 对应的值进行组合
  

• 根节点为 0 和 1 的子树进行比较，17 < 44，17 胜出
  0 作为爷节点，1 作为父节点
  

• 根节点为 0 和 2 的子树进行比较，10 < 17，10 胜出

  2 作为爷节点，0 作为父节点

• 根节点为 2 和 4 的子树进行比较，10 < 15，10 胜出

  2 作为爷节点，4 作为父节点

  

• 可以看出，根节点是 2，其对应的值是 10，也就是{17, 44, 10, 29, 15} 中的最小值，共比较 3 次，比建树时找到最小值所需的比较次数（5次）少

疑问

为什么比较次数减少了？

• 在刚才的例子中，44 没有和 4 的右子树进行比较，这是为什么呢？
  

  • 败者树中，两棵子树的合并规则是：胜者根节点做爷节点，败者做父节点
    因此，编号 3 是败者，编号 4 是胜者

  • 新节点 x 只需要和胜者 y 比较即可

    • 若 x < y，那么 x 可以做根节点，而 y 做父节点
    • 反之 y 做根节点，而 x 做父节点

  • 换句话说，在设定的比较规则中（值小的获胜），我们只关心获胜者（谁是最小的），而不关心节点比哪些节点大

    • 有 2 个集合 A，B，我们想找到两个集合的最小值
      A 集合的最小值是 x
      B 集合的最小值是 y

      显然，要选出最小值，只要比较 x 和 y 即可，若 x < y，那么 x 就是 A 和 B 中最小的，y 比 A 中的哪些元素小，我们并不关心

如果某个归并段的元素一直获胜，没有元素了怎么办？

处理方法 1

• 记录归并段的元素个数，若某个归并段没有元素，则在输出其根节点对应的值后，移除这课子树

• 编号 1 对应的归并段没有元素了，那么输出 5，并移除 5 对应的子树，移除后的败者树被破坏了
  

• 0 和 2 需要重新比较
  

• 2 和 4 重新比较
  

• 败者树又构建好了（ヾ(•ω•`)o）
  

处理方法 2

• 可以填充一个“最大值”，保证所有元素都比最大值小，那么这个最大值就不会在接下来的比较中胜出

• 1 对应的 5 输出，而 1 合并的是 2 和 4

• 假设 999 是最大的值了，类似方法 1，调整一下败者树的结构

2 对应的 10 是 {17, 999, 10, 29, 15} 中的最小值