锦标赛树
一般用于多路归并
胜者树
叶子节点为数据，每层取最大值，直到到达根，根即为最大值。
- 时间初始化 可以用来完成选择排序，
- 每次从根下溯到原叶子节点
- 删去这个节点，逐层上溯更新到根，此时得到次大值
- 每次删去和更新
- 适合用于实现不完全选取：取前 k 大的数。常系数比堆更小，渐近复杂度和堆相同
败者树
内部节点记录每场比赛的败者，需额外记录最终的胜者。 每次更新时，只需和父亲进行比较并更新即可，败者留下，胜者继续向上。
胜者树 vs 败者树
- 胜者树：从叶子节点到根的路径上每次需要访问兄弟节点和父节点，访存次数较多
- 败者树：每层只需访问父节点，访存次数少