多路平衡归并

败者树

分支(内部/非叶子结点):存两场比赛【败者】的归并段号!

比赛:两个候选元素PK,关键字大的是败者,留在父(分支)结点;关键字小(胜者)往上继续比赛。

👉✅分支(内部节点)存较大元素所在段号(败者)

真正全局冠军(最小元素,较小的那个)放在额外增加的 ls[0],挂在根节点上 不是二叉树的根!!!根节点存的是败者的段号

败者树

置换选择排序

注意 工作区满了的时候,不是一下子把工作区的内容输出到新的归并段,而是输出一个补一个

最佳归并树

会判断要补充多少个虚段

最后修改:2026 年 07 月 31 日