## 一、败者树（Loser Tree）基础 ### 1. 败者树的定义 - 一种**完全二叉树**，常用于多路归并、优先队列。 - 每个**内部节点**存储“败者”（比较中的较小值或较大值，取决于目标）。 - **胜者**继续向上比较，最终根节点 `tree[0]` 存储全局胜者。 - 叶子节点对应外部数据（如多个有序数组的当前首元素，或数组元素本身）。 ### 2. 败者树 vs 胜者树 - 胜者树：内部节点存胜者。 - 败者树：内部节点存败者，胜者继续向上，**调整时只需沿一条路径向上**，效率更高。 - 败者树单次调整时间复杂度：`O(log n)`。 ### 3. 核心调整函数 `adjust` void adjust(int index) { int parent = get_parent(index); while (parent > 0) { if (segments[index].empty() || segments[index].front() > segments[tree[parent]].front()) { std::swap(index, tree[parent]); } parent = get_parent(parent); } tree[0] = index; } - 当某个叶子节点值变化后，从该叶子向上调整。 - 比较当前节点与父节点存储的败者，必要时交换。 - 最终 `tree[0]` 更新为新的胜者。 --- 上一篇: [[计算机系/算法分析与设计/04 递归与分治算法|上一篇]] 前置知识: [[计算机系/算法分析与设计/04 递归与分治算法|前置知识]] # 败者树与多路归并 ## 二、败者树的两种应用场景 ### 1. 多路归并（分段数组） - `segments` 是多个有序数组。 - 败者树维护各段当前最小值的索引。 - 每次取出最小值后，对该段调用 `adjust`。 - 适用于外部排序、K 路归并。 ### 2. 单数组找最大/次大值 - 输入是一个完整数组 `A[0..n-1]`，不是分段数组。 - 把数组元素当作叶子节点，构建败者树。 - 通过反转比较方向（`>` 而不是 `<`），可以构建“最大败者树”。 - 根节点 `tree[0]` 指向最大值。 --- ## 三、找最大值和次大值的算法 ### 1. 问题要求 - 给定数组 `A[0..n-1]`。 - 在最坏情况下用 **n + log n** 次比较找出最大值和次大值。 ### 2. 核心思想 - **最大值**：通过败者树（或锦标赛树）两两比较，`n - 1` 次比较即可找到。 - **次大值**：一定出现在**与最大值直接比较过的元素**中。 - 在败者树中，最大值从叶子到根的路径长度为 `log n`。 - 路径上每个内部节点存储的败者，就是与最大值比较过的元素。 - 候选集大小 ≤ `log n`。 - **在候选集中找最大**：`log n - 1` 次比较。 - **总比较次数**：`(n - 1) + (log n - 1) = n + log n - 2 ≤ n + log n`。 ### 3. 关键结论 - 次大值**不需要重新建树**，只需从最大值的比较路径中收集败者。 - 不能通过“删除最大值后重建树”来找次大值，因为： - 会破坏原数组； - 额外增加 `n - 1` 次比较，超出 `n + log n` 限制。 --- ## 四、代码实现中的常见错误 ### 1. 比较方向反了 - 败者树默认找最小值（`<`）。 - 找最大值需要反转比较逻辑（`>`）。 - 如果方向反了，根节点会指向最小值而不是最大值。 ### 2. 次大值查找方式错误 - 错误做法：`A.remove(max_val)` 后重新建树。 - 正确做法：从 `tree[0]` 向上回溯，收集路径上的败者，再取最大值。 ### 3. 父节点计算错误 - 完全二叉树中，更稳妥的父节点公式是 `(index - 1) // 2`。 - 用 `index // 2` 在某些索引结构下会出错。 ### 4. 建树方向错误 - 应从最后一个叶子节点向上调整，而不是从 `n//2 - 1` 开始。 - 初始化时每个叶子先作为候选胜者。 --- ## 五、正确实现的关键步骤 1. **初始化**：`tree[i] = i`，每个叶子都是候选胜者。 2. **建树**：从 `n-1` 到 `1`，依次调用 `adjust(i)`。 3. **找最大值**：`max_val = A[tree[0]]`。 4. **收集候选**：从 `tree[0]` 沿父节点路径向上，收集 `A[tree[parent]]`。 5. **找次大值**：在候选集中取最大值。 6. **比较次数**：严格满足 `n + log n - 2`。 --- ## 六、复杂度与正确性分析 |阶段|操作|比较次数| |---|---|---| |建树|每个内部节点一次比较|n - 1| |收集候选|沿路径向上，无比较|0| |找次大值|在 log n 个候选中找最大|log n - 1| |**总计**||**n + log n - 2**| - 时间复杂度：`O(n)`（建树）+ `O(log n)`（找次大）= `O(n)`。 - 空间复杂度：`O(n)`（tree 数组）。 - 满足题目“最坏情况下 n + log n 次比较”的要求。 --- ## 七、总结性知识点 1. **败者树的核心**：内部节点存败者，胜者向上，根节点存全局胜者。 2. **adjust 函数**：叶子变化后沿路径向上调整，`O(log n)`。 3. **找最大值**：建最大败者树，`n - 1` 次比较。 4. **找次大值**：最大值路径上的败者中的最大值，`log n - 1` 次比较。 5. **总比较次数**：`n + log n - 2`，满足要求。 6. **常见错误**：比较方向反、删除最大值重建树、父节点计算错、建树方向错。 7. **正确做法**：不修改原数组，回溯收集候选，再取最大。