败者树

2025年6月1日

多路归并外排序: 败者树

外排序基本思想

外排序是指数据量太大，无法一次性全部装入内存时，借助外存（磁盘）进行排序。常用方法是多路归并排序，即先将数据分成若干“归并段”，每次归并时只将部分数据读入内存。一般来说它的优点有这三种：

处理大规模数据集：当数据集太大，无法在计算机的内存中完全装入时，外部排序算法是一个很好的选择。例如，在处理大型数据库或超大规模文件时，通常需要使用外部排序算法。
节约内存：当内存受限时，外部排序算法也是很有用的。例如，在移动设备等资源受限的计算机上运行排序操作时，使用外部排序算法可以避免占用过多的内存。
并行处理：外部排序算法还可以通过将数据集分成多个块并对每个块进行并行处理来进一步提高性能。这意味着可以使用多个处理器或计算机来同时处理数据集，从而加快排序速度。

败者树就是为了并行处理，而构造的一种树。

多路归并排序

想象一下，家里突然来了一大堆快递包裹，每个包裹里装着不同年代的明信片。我想把所有明信片按时间顺序排列，但家里的桌子太小，没办法一次性摊开全部包裹。怎么办？只能分批处理——这就是“外排序”的现实版，没法直接一次性处理好这些数据。

多路归并排序的套路就像开 k 个快递包裹，每次从每个包裹里抽一张最特殊的明信片（最年代久远的，或者是最年轻的），摆成一排，不断重复，直到所有包裹都拆完。最后我们就得到了一个基于特殊程度顺序的，明信片排列。我们把所有的拆开，一步一步组合，最后得到归并顺序，这就是k 路归并。

一开始我们只有使用堆来完成多路归并，但是人们发现堆每次取出最小值之后，把最后一个数放到堆顶，调整堆的时候，每次都要选出父节点的两个孩子节点的最小值，然后再用孩子节点的最小值和父节点进行比较，所以每调整一层需要比较两次。

这时人们想能否简化比较过程，这时就有了胜者树：这样每次比较只用跟自己的兄弟节点进行比较就好，所以用胜者树可以比堆少一半的比较次数。

而胜者树在节点上升的时候，需要获得父节点，然后再获得兄弟节点，然后再比较，判断要不要上升。这时人们又想能否再次减少读取节点的次数，于是就有了败者树。

在使用败者树的时候，每个新元素上升时，只需要获得父节点并比较即可。

那么胜者树，败者树到底有什么区别呢？

败者树是胜者树的一种变体，它也是一棵完全二叉树。和胜者树不同的是，败者树的节点存储的是败者。一般采用数组模拟胜者树或败者树的结构，所以胜者树、败者树选哪一个都行，胜者树相比败者树要少维护一个冠军项。败者树便于查找、更新和归并输出胜者。

败者树结构与实现

败者树的结构图

基础图形，特殊于树顶有一个唯一值胜者：

graph TD
	W["🥇胜者的索引 i"]
    A["🥈败者第1名的索引 i"]
    B1["败者索引 i"]
    B2["败者索引 i"]
    C1["选手1"]
    C2["选手2"]
    C3["选手3"]
    C4["选手4"]
    W --> A
    A --> B1
    A --> B2
    B1 --> C1
    B1 --> C2
    B2 --> C3
    B2 --> C4

基础分析（定最小者赢）：

建树与维护过程

建立败者树

让我们建立一个败者树，ls[0], ls[1], ls[2], ls[3], ls[4] 是败者树的内部节点（即非叶子节点），存储每一轮败者的索引，b0~b4是败者树的叶子节点。败者树的每个节点存储的都是两两比较的败者（数大者败，我们先要求出的是各归并路中的最小嘛）在原数组中的索引。

b3 和 b4 比较，b3 < b4, b4 败。所以父节点 ls[4]=4. 胜者是 b3, 所以 3 就晋级下一轮与 b0 比较（图中树的边上的数字就是晋级的选手编号）
b0 与 b3 比较, b3 < b0, b0 败, 所以父节点 ls[2]=0, 胜者是 b3，所以 3 就晋级下一轮与另一边晋级的比较
b1 与 b2 比较, b1 < b2, b2 败, 所以父节点 ls[3]=2. 胜者是 b1, 所以1就晋级下一轮与 b3会师总决赛。
b1 与 b3 比较, b3 < b1, b1 败, 所以父节点 ls[1]=1. 胜者是 b3, 所以 ls[0] 记录最终胜者3。排序最小值，算法输出 b[3]（原数组中最小）。最后构造成功：

graph TD

    subgraph "最终败者树结构与节点值"
        LS0_final["ls[0]=3 (总胜者索引)"]
        LS1_final["ls[1]=1 (败者索引)"]
        LS2_final["ls[2]=0 (败者索引)"]
        LS3_final["ls[3]=2 (败者索引)"]
        LS4_final["ls[4]=4 (败者索引)"]

        B0_f["b0 (10)"]
        B1_f["b1 (5)"]
        B2_f["b2 (8)"]
        B3_f["b3 (2)"]
        B4_f["b4 (12)"]

        LS0_final --> LS1_final
        LS1_final --> LS2_final
        LS1_final --> LS3_final
        LS2_final --> B0_f
        LS2_final --> LS4_final
        LS4_final --> B3_f
        LS4_final --> B4_f
        LS3_final --> B1_f
        LS3_final --> B2_f

        style LS0_final fill:#90EE90,stroke:#006400,stroke-width:2px
        style LS1_final fill:#D3D3D3,stroke:#333
        style LS2_final fill:#D3D3D3,stroke:#333
        style LS3_final fill:#D3D3D3,stroke:#333
        style LS4_final fill:#D3D3D3,stroke:#333
        style B3_f fill:#ADFF2F,stroke:#333 %% Highlight the winner leaf
    end

    %% Styling
    classDef playerNode fill:#FFFACD,stroke:#B8860B,stroke-width:1px;
    class B0,B1,B2,B3,B4 playerNode;
    class B0_f,B1_f,B2_f,B3_f,B4_f playerNode;

    classDef stepNode fill:#ADD8E6,stroke:#4682B4,stroke-width:1px,border-radius:5px;
    class Step1,Step2,Step3,Step4,Step5 stepNode;

    classDef winnerNode fill:#FFA07A,stroke:#CD5C5C,stroke-width:1px,shape:capsule;
    class Step1_W,Step2_W,Step3_W,Step4_W winnerNode;

维护败者树

我们一般用”更新”来说明败者树的维护：

我们来了一个新的成员，走了一个成员，想要让它加入后重塑这颗树，实现败者树的更新。可以想象成晋级赛：上一轮的冠军带着“新人”重新参加比赛，只需要重新打一遍自己走过的那条“晋级之路”，而其它归并段（叶子）完全不用重新比较。每次归并输出和更新，最多只需要 $\log_2 k$ 次比较。

graph TD
    direction TB
    %% 败者树维护（插入/替换）后的状态
    %% 原冠军 b3(值2) 被 新b3(值6) 替换
    %% 调整后, 新冠军为 b1(值5)

    LS0_m["ls[0]=1 (新胜者: b1[5])<br/>(原ls[0]=3)"]
    LS1_m["ls[1]=3 (新败者: 新b3[6])<br/>(原ls[1]=1)"]
    LS2_m["ls[2]=0 (败者: b0[10])<br/>(调整路径节点, 值未变)"]
    LS3_m["ls[3]=2 (败者: b2[8])<br/>(非调整路径节点)"]
    LS4_m["ls[4]=4 (败者: b4[12])<br/>(调整路径节点, 值未变)"]

    B0_m["b0 (10)"]
    B1_m["b1 (5)"]
    B2_m["b2 (8)"]
    B3_m["新b3 (6)<br/>(原b3值: 2)"]
    B4_m["b4 (12)"]

    LS0_m --> LS1_m
    LS1_m --> LS2_m
    LS1_m --> LS3_m
    LS2_m --> B0_m
    LS2_m --> LS4_m
    LS4_m --> B3_m
    LS4_m --> B4_m
    LS3_m --> B1_m
    LS3_m --> B2_m

    classDef defaultLeaf fill:#FFFACD,stroke:#B8860B;
    classDef changedLeaf fill:#lightblue,stroke:#0000FF,stroke-width:2px,font-weight:bold;
    classDef newWinnerLeaf fill:#ADFF2F,stroke:#006400,font-weight:bold;
    
    classDef pathChangedNode fill:#90EE90,stroke:#006400,stroke-width:2px,font-weight:bold;
    classDef pathUnchangedNode fill:#lightyellow,stroke:#333,stroke-width:1px,stroke-dasharray:5 5;
    classDef notOnPathNode fill:#D3D3D3,stroke:#333;

    class LS0_m,LS1_m pathChangedNode;
    class LS2_m,LS4_m pathUnchangedNode;
    class LS3_m notOnPathNode;
    
    class B0_m,B2_m,B4_m defaultLeaf;
    class B3_m changedLeaf;
    class B1_m newWinnerLeaf;

我们插入一个新的节点 b5 (4)，步骤也很简单：

让新选手 b5 与现有选手 b4 进行比赛。我们需要一个新的内部节点（我们称之为 ls[5]）来存储这场比赛的败者。

b5(4) vs b4(12)：胜者是 b5(4)，败者是 b4(12)。所以 ls[5] 记录败者 b4 的索引 4。
然后，这场 (b5 vs b4) 的胜者 (b5) 再与原先和 b4 比赛的 b3 进行比赛。原先存储 (b3 vs b4) 败者的节点 ls[4] 现在将存储这场 (b3 vs 胜者(b5,b4)) 比赛的败者。 b3(2) vs b5(4)：胜者是 b3(2)，败者是 b5(4)。所以 ls[4] 记录败者 b5 的索引 5。
这个胜者 b3(2) 继续沿用原有的路径向上比赛：与 b0(10) 比赛：胜者 b3(2)，败者 b0(10)。ls[2] 记录败者 b0 的索引 0 (此节点值未变)。
树的另一分支 (b1 vs b2) 不受影响： b1(5) vs b2(8)：胜者 b1(5)，败者 b2(8)。ls[3] 记录败者 b2 的索引 2 (此节点值未变)。
最终决赛：来自 ls[2] 分支的胜者 b3(2) vs 来自 ls[3] 分支的胜者 b1(5)：胜者 b3(2)，败者 b1(5)。ls[1] 记录败者 b1 的索引 1 (此节点值未变)。
总冠军： ls[0] 记录总冠军 b3 的索引 3 (此节点值未变)。

graph TD
    direction TB
    %% 败者树添加新节点 b5(4) 后的状态
    %% 原有选手: b0(10), b1(5), b2(8), b3(2), b4(12)
    %% 新增选手: b5(4) (值为4, 索引为5)
    %% 数小者胜

    LS0["ls[0]=3 (总胜者: b3[2])"]
    LS1["ls[1]=1 (败者: b1[5])"]
    LS2["ls[2]=0 (败者: b0[10])"]
    LS3["ls[3]=2 (败者: b2[8])"]
    LS4_mod["ls[4]=5 (败者: b5[4])"  ]
    LS5_new["ls[5]=4 (败者: b4[12]) "]

    B0["b0 (10)"]
    B1["b1 (5)"]
    B2["b2 (8)"]
    B3["b3 (2)"]
    B4["b4 (12)"]
    B5["b5 (4)"]

    LS0 --> LS1
    LS1 --> LS2
    LS1 --> LS3
        LS2 --> B0
        LS2 --> LS4_mod
            LS4_mod --> B3
            LS4_mod --> LS5_new  
                LS5_new --> B4
                LS5_new --> B5
        LS3 --> B1
        LS3 --> B2

    classDef defaultLeaf fill:#FFFACD,stroke:#B8860B;
    classDef newLeaf fill:#FFDAB9,stroke:#FF8C00,font-weight:bold;
    classDef winnerLeaf fill:#ADFF2F,stroke:#006400,font-weight:bold;
    
    classDef winnerNode fill:#90EE90,stroke:#006400,stroke-width:2px,font-weight:bold;
    classDef loserNode fill:#D3D3D3,stroke:#333; 
    classDef newInternalNode fill:#E6E6FA,stroke:#9370DB,font-weight:bold; 
    classDef modifiedInternalNode fill:#ADD8E6,stroke:#4682B4,font-weight:bold; 

    class LS0 winnerNode;
    class LS1,LS2,LS3 loserNode;
    class LS4_mod modifiedInternalNode;
    class LS5_new newInternalNode;

    class B0,B1,B2,B4 defaultLeaf;
    class B3 winnerLeaf;
    class B5 newLeaf;

在多路归并排序里，败者树实现比胜者树更高效、更容易维护。更新只需沿着冠军的路径向上“重新比一遍”，而不用全部重算。

代码实现与多路归并文件流

败者树的实现比较基础，其实和堆的构建很相似，我们做的是与相邻节点一直比较，然后将失败节点放在最上端即可。这种排序思想其实与堆排序思想相似，败者树的优势在于我们处理查找最佳者，次佳者操作，效率更高。外排序的效率瓶颈从算法到了数据读取，胜者树和败者树都是很伟大的数据结构。

LoserTree 基本模板类例：

// 败者树类模板，T为可比较类型，最小值胜
template<typename T>
class LoserTree {
public:
    // k为路数，sources为每一路的当前元素
    LoserTree(const std::vector<T>& sources)
        : k(sources.size()), leaves(sources), ls(k, -1) {
        build();
    }

    // 返回当前最小元素的下标
    int winner() const {
        return winnerIdx;
    }

    // 输出冠军，并用新元素替换，维护树结构
    void popAndReplace(T newElem) {
        leaves[winnerIdx] = newElem;
        adjust(winnerIdx);
    }

    // 获取当前冠军的值
    T top() const {
        return leaves[winnerIdx];
    }

private:
    int k;                      // 路数
    std::vector<T> leaves;      // 叶子节点（各路的当前值）
    std::vector<int> ls;        // 内部节点，存败者编号
    int winnerIdx;              // 当前冠军编号

    // 建树：从叶子到根层层比较，初始化ls和winnerIdx
    void build() {
        ls.assign(k, -1);
        winnerIdx = 0;
        for (int i = 0; i < k; ++i) {
            if (leaves[i] < leaves[winnerIdx]) winnerIdx = i;
        }
        for (int i = 0; i < k; ++i) {
            if (i != winnerIdx) adjust(i);
        }
    }

    // 从叶i出发向上挑战，维护败者树
    void adjust(int i) {
        int parent = (i + k) / 2;
        int challenger = i;
        while (parent > 0) {
            // challenger与ls[parent]决出胜负，胜者上移
            if (leaves[challenger] < leaves[ls[parent]]) {
                std::swap(challenger, ls[parent]);
            }
            parent /= 2;
        }
        // 根节点与当前winner比较
        if (leaves[challenger] < leaves[winnerIdx]) {
            std::swap(challenger, winnerIdx);
        }
        // 最终winnerIdx存冠军下标
    }
};

基本使用：

std::vector<int> sources = {7, 9, 4, 6}; // 各路的初始元素
LoserTree<int> tree(sources);
std::cout << "当前冠军编号: " << tree.winner() << ", 元素: " << tree.top() << std::endl;

// 假设弹出冠军后，路3有新元素8
tree.popAndReplace(8);
std::cout << "新冠军编号: " << tree.winner() << ", 元素: " << tree.top() << std::endl;

结合文件流，多文件编程，我们可以对于多路归并，利用败者树，实现外排序：我们写个文件头 LoserTree.h，比较好引用：

//LoserTree.h
#ifndef LOSERTREE_H
#define LOSERTREE_H

#include <vector>
#include <limits>
#include <memory>

// ------- 单路输入流接口（可扩展为文件流/数组流/网络流等） -------
struct InputStream {
    virtual bool next(int& val) = 0;
    virtual ~InputStream() {}
};

// 败者树类，适合多路归并外排序
class LoserTree {
public:
    // 构造函数：输入k路流
    LoserTree(std::vector<std::unique_ptr<InputStream>>& streams);

    int winner() const;    // 当前冠军编号
    int top() const;       // 当前最小元素
    void popAndReplace();  // 输出冠军，补新元素，维护树结构
    bool empty() const;    // 判断是否归并结束

private:
    const int INF = std::numeric_limits<int>::max();
    int k;
    std::vector<int> leaves;  // 当前各路的元素
    std::vector<int> ls;      // 内部节点存败者编号
    int winnerIdx;            // 冠军编号
    std::vector<std::unique_ptr<InputStream>>& input_streams;

    void build();             // 初始建树
    void adjust(int i);       // 沿冠军路径维护
};

#endif // LOSERTREE_H

#include "LoserTree.h"
#include <iostream>

// 数组流实现
struct VectorInputStream : public InputStream {
    const std::vector<int>& arr;
    size_t pos;
    VectorInputStream(const std::vector<int>& a) : arr(a), pos(0) {}
    bool next(int& val) override {
        if (pos < arr.size()) {
            val = arr[pos++];
            return true;
        }
        return false;
    }
};

int main() {
    std::vector<int> arr1{2, 5, 9};
    std::vector<int> arr2{1, 4, 7, 11};
    std::vector<int> arr3{3, 8, 12};

    std::vector<std::unique_ptr<InputStream>> streams;
    streams.emplace_back(new VectorInputStream(arr1));
    streams.emplace_back(new VectorInputStream(arr2));
    streams.emplace_back(new VectorInputStream(arr3));

    LoserTree lt(streams);

    std::cout << "败者树多路归并结果：";
    while (!lt.empty()) {
        int val = lt.top();
        if (val != std::numeric_limits<int>::max())
            std::cout << val << " ";
        lt.popAndReplace();
    }
    std::cout << std::endl;
    return 0;
}

只需实现 InputStream 接口，LoserTree 就能无缝适配各种归并源（如大文件、分布式流、数据库游标），这也是它工程实践中的巨大优势。

应用

败者树是非常高效的数据结构，适用于各种排序和选择问题。在实际应用中，我们可以根据具体问题选择使用胜者树或败者树。对于需要频繁更新数据集的问题，胜者树是一个更好的选择；对于需要快速记录和查找比赛结果的问题，败者树则更加适用。这两种数据结构都可以在 log (n) 时间内完成最值查找和更新操作，具有很高的实用价值。

大型搜索引擎的“网页排名归并”

比如你在百度、Google 搜索同一个关键词时，背后往往有成百上千台服务器分别给你算出“最相关的网页排名”，但最后这些排名结果需要快速合并成一个全局排名列表。
败者树就像一场高效的“锦标赛”，每次都能最快选出全体中“最优网页”，把全球各地的“榜首网页”按序输出，大大提高搜索响应速度。

云盘/网盘的多服务器文件同步

比如阿里云盘、百度网盘要把全球多台服务器上的同步文件合成一个最终的时间线展示，这时候每台服务器的文件变动已经排好序，只需归并各路“文件事件”流。
败者树就是最好的选择，保证“最近的更新”总能优先显示，哪怕有成百上千台服务器，也能稳定工作。

视频推荐系统的“多路个性化候选集归并”

你刷 B 站/抖音时，推荐系统会从无数个“兴趣通道”各自找出适合你的视频，最后要把这些小列表合并成全局排序，推荐给你。
败者树可以把多个候选池（比如“你喜欢的音乐”、“你最近常看的 UP 主”、“全站热点”等）合并，保证每次推送的都是最优解。

败者树不仅限于排序数字流，它适合任何有序对象的高效归并——比如合并新闻流、股票行情、快递物流进度等。在分布式大数据场景下，败者树和胜者树比传统堆/优先队列更高效，尤其适合“路数极多”的超级归并任务。只要你能把生活中的“多路有序队列”抽象成 InputStream，败者树就能帮你把它们归并成一条高效、无遗漏的“大路”。

性能优缺点分析

时间复杂度

建树（初始化）

建树过程需要让每一个叶子节点沿路径挑战至根，共 $k$ 路，每次最多比较 $\log_2 k$ 次，总体复杂度为 $O(k \log k)$ 。

归并操作（每次输出最小值）

每次归并输出，新元素替换后，只需要沿冠军路径向上“重新比较”一遍，最多 $\log_2 k$ 层。
因此，每次归并输出/更新的时间复杂度为 $O(\log k)$ 。
对于 $n$ 个总元素归并排序，总体复杂度为 $O(n \log k)$ 。

这一点比直接用暴力遍历所有路（ $O(k)$ ）快得多，特别适合 $k$ 很大时使用。

空间复杂度

败者树本身维护一个完全二叉树结构，含 $k$ 个叶子和 $k$ 个内部节点（每个内部节点只需存一个路的索引或指针）。
主要需要存储：
- $k$ 个叶节点（每路当前值，实际归并中只需一个元素的缓存/指针）
- $k$ 个内部节点（败者索引或指针）
空间复杂度总为 $O(k)$ 。

与其他归并方法对比

暴力归并：每次都遍历所有 $k$ 路，查找最小元素，时间复杂度 $O(nk)$ 。
堆/优先队列归并：每次插入弹出堆顶都是 $O(\log k)$ ，和败者树同阶，但败者树常数更小，且可更好地复用内存，更新效率高。
败者树：在 $k$ 很大时（如数百、上千路归并），败者树的效率更明显。

优点

每次找最小值、更新树只需 $O(\log k)$ ，对大规模归并非常友好。
空间消耗小，易于实现。
特别适合归并段数量多、单段数据量小的场景。

缺点

实现比暴力法复杂一点，初学者需要适应树结构。
归并段不均衡时，可能存在部分节点重复挑战，导致更新稍慢。

败者树