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

前置知识

归并段

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

建树过程

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

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

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

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

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

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

  

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

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

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

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

比较过程

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

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

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

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

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

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

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

  

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

疑问

为什么比较次数减少了

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

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

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

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

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

    • 有 2 个集合 AB我们想找到两个集合的最小值
      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} 中的最小值