败者树通过复用历史比较结果，将每轮选最小元素的比较次数从k-1次降至⌈log₂k⌉次：仅需沿胜者上升路径更新败者，路径长度即树高，避免重新两两比较全部k个元素。
败者树为什么比直接比较更省比较次数
败者树本质是维护 K 个子序列当前最小元素的“局部淘汰关系”，它把每轮归并中 K-1 次两两比较压缩成 log₂K 次比较——不是靠减少单次归并的比较，而是靠复用历史比较结果。每次只替换一个叶节点（即某路新读入的元素），然后从该叶子向上重算路径上的“败者”，路径长度就是树高 log₂K，而不用重新拉通所有 K 个元素两两比一遍。
构建败者树时别把 winner 当成 root
常见错误是误以为败者树的根节点存的是胜者（最小值），其实 loser_tree[0] 存的是“最终失败者”，真正胜者藏在额外变量 winner 里。初始化时必须显式选出第一个胜者，再让其余 K−1 个元素逐个和当前胜者比、把败者填进对应内部节点。否则会漏掉一次关键比较，导致首趟归并就出错。
- 建树循环要从
i = K开始倒推，对每个内部节点i计算loser[i] = (tree[2*i] （假设数组下标从 1 开始） - 叶子层（下标
K到2*K-1）必须预加载各路首元素，不能留空或用哨兵值覆盖真实数据 - 如果 K 不是 2 的整数次幂，需补虚拟路（用
INT_MAX等哨兵），但补的路不能参与实际归并，否则比较次数反而上升
adjust() 函数里只更新一条路径，别重算整棵树
每次从某路取出胜者后，必须从对应叶子位置向上调整：设该路编号为 id，则其叶子索引为 leaf = K + id，之后只沿 leaf → leaf/2 → leaf/4 → … → 1 这条路径更新内部节点，每步只做 1 次比较（拿当前节点的两个孩子比，败者存入该节点）。任何偏离这条路径的遍历（比如 for 循环扫所有内部节点）都会让复杂度退化到 O(K)。
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
void adjust(int id, const vector<int>& current, vector<int>& loser_tree, int& winner) {
int pos = K + id;
int cmp = winner;
while (pos > 1) {
int parent = pos / 2;
if (current[loser_tree[parent]] < cmp) {
swap(loser_tree[parent], pos);
cmp = current[loser_tree[parent]];
}
pos = parent;
}
winner = current[id]; // 注意：这里 winner 是本轮新胜者，不是 loser_tree[0]
}
败者树真正的省时点在 I/O-bound 场景下
当 K 路数据来自磁盘或网络（比如外部排序），每次比较代价远小于一次 I/O 时，败者树的价值才凸显——它把每输出 1 个元素所需的平均比较次数从 K−1 压到 log₂K，同时保证每路只需维持 1 个缓冲区元素。但如果所有数据已在内存且 K 很小（如 K ≤ 4），手写 min({a,b,c,d}) 反而更快，因为败者树的指针跳转和缓存不友好可能抵消理论优势。
立即学习“C++免费学习笔记（深入）”；
实际调参时，K 取 8～32 较平衡；超过 64 后树高增长变缓，但节点分支预测失败率上升，得测具体硬件。别迷信公式里的 log，Cache Line 对齐和内存局部性往往比比较次数影响更大。
