胜者树/败者树Tournament Tree— 外排序的核心引擎055胜者树从体育锦标赛到大数据引擎5W1H 发明者故事Who何人- 发明者是谁发明者竞标赛排序Tournament Sort的思想来源于多人但将其系统化为数据结构并应用于外排序的是 Donald E. Knuth在 TAOCP 第三卷第 5.4.1 节中给出了完整的理论分析。历史渊源体育竞标赛的思想单淘汰赛决出冠军在人类文明中有数千年历史将竞标赛思想用于排序由 Knuth 在 1973 年出版的 TAOCP 第三卷中系统阐述败者树Loser Tree作为胜者树的变体由 Knuth 在同一节中分析实现上更高效IBM 的工程师在 1950 年代开发磁带排序时已在实践中使用类似思想When何时- 什么时候发明的时间作为数据结构被系统记录于 1973 年 TAOCP 第三卷出版时代背景1950-70 年代计算机内存极为有限KB 量级处理大文件必须依赖磁带/磁盘外排序External Sorting是这一时期最重要的实际计算问题之一IBM 701、IBM 7090 等主机的磁带排序性能直接影响商业价值K 路归并K-way merge是外排序的核心而高效选择最小元素是 K 路归并的瓶颈Where何地- 在哪里发明的地点理论系统化于斯坦福大学Knuth 的工作地实践源于 IBM 研究中心环境IBM 主导着 1950-60 年代的商业计算对排序效率有极大的实际需求斯坦福大学的 TAOCP 项目将这些工程实践提升为严格的数学理论Knuth 在写作 TAOCP 时大量参考了 IBM 的技术报告和实际系统设计What何事- 发明了什么数据结构胜者树Winner Tree/ 败者树Loser Tree胜者树结构完全二叉树叶节点为参赛选手待归并序列的当前元素内部节点记录其两个子节点中的胜者最小值的下标根节点记录全局冠军所有叶节点中的最小值0 ← 根记录冠军下标叶节点0最小 / \ 0 2 ← 内部节点记录各子树中的胜者下标 / \ / \ 0 1 2 3 ← 叶节点选手下标 [2][5][3][8] ← 选手值关键操作 replay重赛当冠军被取出后该叶节点更新为新值只需沿该叶到根的路径重新比较O(log K) 时间完成其他 K-1 条路径不需要重新比较关键优化Why何因- 为什么发明要解决的问题K 路归并时每次选择 K 个序列的最小元素朴素比较需要 K-1 次比较在外排序中K 可能很大几十到几百路每次 K-1 次比较代价太高需要一种数据结构在更新一个元素后能以 O(log K) 时间重新找到最小元素理论依据胜者树将 K 路选择从 O(K) 降至 O(log K)每次 replay 只比较 log K 次N 个元素 K 路归并总比较次数N·log K而非朴素的 N·K败者树进一步减少了比较中的数据移动内部节点记录败者而非胜者当时的挑战证明完全二叉树结构能够正确维护冠军设计 replay 操作使其只沿一条路径更新处理边界情况选手数不是 2 的幂、某个序列耗尽How何果- 如何实现有什么影响K 路归并外排序流程1. 初始化从 K 个有序子序列各取第一个元素作为叶节点 2. 建树自底向上每个内部节点取子节点中较小者的下标 3. 循环 a. 输出根所指叶节点的值冠军 b. 从该冠军所在序列读入下一个元素若序列耗尽则设为 ∞ c. 执行 replay从该叶向上重新比较更新路径上各内部节点 d. 直到所有序列耗尽性能对比方法每次选择代价N 元素 K 路归并总代价线性扫描O(K)O(N·K)胜者树O(log K)O(N·log K)败者树O(log K)常数更小O(N·log K)历史影响外排序至今仍是数据库和大数据系统的核心操作MySQL、PostgreSQL 的外部排序均使用类似的多路归并思想Hadoop MapReduce 的 shuffle/merge 阶段使用败者树Apache Spark 的排序算子也基于类似原理TAOCP 中的败者树分析是算法工程化的经典案例今天的使用数据库外排序ORDER BY 大表时大数据框架Hadoop、Spark的 K 路归并流处理系统的多源有序流合并磁盘 B 树的顺序扫描优化自然语言需求定义需求名称实现胜者树支持初始化、查询冠军、更新叶节点后重赛并模拟 K 路归并的外排序场景功能需求用精确的中文描述初始化build_winner_tree根据叶节点初始值构建胜者树输入叶节点值数组、叶节点数量 K操作自底向上每个内部节点取子节点中较小值的下标输出无就地填充 winner 数组查询冠军get_winner返回当前最小值输入胜者树结构体指针操作返回根节点所指叶节点的值输出最小值若树为空返回 INT_MAX更新并重赛replay更新某个叶节点的值后重新竞争输入胜者树结构体指针、叶节点下标、新值操作更新叶节点值从该叶节点向上逐层重新比较更新路径上各内部节点输出无就地更新 winner 数组K 路归并模拟模拟将 K 个有序序列合并为一个有序序列输入K 个有序子数组及其长度操作建树 → 循环取冠军 → 更新对应序列的下一个元素 → replay输出填充合并后的有序数组约束条件胜者树为完全二叉树叶节点个数 K 必须为 2 的幂或需处理非 2 的幂情况内部节点数组下标根为下标 0 或 1根据实现选择需注释说明叶节点下标 k 的父节点下标为 (k K - 1) / 20-based或类似公式当序列耗尽时将对应叶节点设为 INT_MAX哨兵值实现最小胜者树最小值为冠军验收标准表格编号测试场景自然语言描述预期结果验证方式18叶节点值 [2,5,3,8,1,7,4,6]查询冠军1最小值断言等于 12取出冠军后将叶5值1更新为 10重赛后冠军2断言等于 23继续取出冠军并更新模拟序列耗尽用 INT_MAX冠军依次递增断言有序48叶节点值 [8,7,6,5,4,3,2,1]查询冠军1断言等于 154路归并[1,5,9]、[2,6,10]、[3,7,11]、[4,8,12]有序序列 1~12断言数组各元素64路归并长度不等的序列 [1,3]、[2,4,6,8]、[5]、[7,9]有序序列 1~9断言数组各元素7单叶节点胜者树K1冠军为该叶值叶节点值断言8所有叶节点值相同均为 5冠军为 55断言等于 5C语言实现文件对应文件:winner_tree.c编译运行:gcc-stdc99-Wall-owinner_tree_test winner_tree.c ./winner_tree_test核心函数:build_winner_tree(wt, leaves, k)— 初始化胜者树get_winner(wt)— 返回当前冠军值replay(wt, leaf_idx, new_val)— 更新叶节点并重赛kway_merge(seqs, lens, k, output, out_size)— 模拟 K 路归并winner_tree_free(wt)— 释放内存