败者树是计算机科学学科里的一种数据结构，可用于外部排序中提高效率。实际上是一棵完全二叉树。

败者树的中间结点记录的败者的标号 它可以在 log(n) 时间内找到最值。

败者树的建立：在参赛者数组b[]的最后添加一位，存放一个参赛选手的绝对最小值（选手都是正数的话，如-1）。所有中间节点都记录这个最小值的下标。然后依次调整（adjust()）各个选手即可。

败者树的调整：当改变一个选手的值，需要调整以维持败者树的形态。败者树只需调整选手的父节点即可。当子节点的值大于父节点，则子节点记录于父节点（小为胜利，记录败者），父节点继续与其父节点比赛；若子节点小于父节点，则直接使用子节点进行下一轮比赛。

如图所示是一颗败者树，规定数大者败。

败者树
败者树
  • b0与b1对比，b0败
  • b2与b3对比，b3败
  • b1与b2对比，b2败

ls[0]记录的是胜者的下标

相关实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <stdio.h>
#include <string.h>
#define LEN 4
#define MIN -1

int buf[LEN+1];// 存放多路归并的头元素，多出来的一位放最小值
int ls[LEN+1]; // ls[0]保存的是胜者的下标，其余保存败者下标号

inline void adjust(int index, int *arr) {
    int tmp = (index+LEN)>>1;

    while (tmp > 0) {
        if (buf[index] > buf[ls[tmp]]) { // 如果当前节点大于父节点（胜者）
            ls[tmp] ^= index; // 交换两个数的异或做法
            index ^= ls[tmp];
            ls[tmp] ^= index;
        }
        tmp /= 2; // 访问父节点
    }
    ls[0] = index; // ls[0] 记录最小值的标号
}

inline void build(int *arr) {
    buf[LEN] = MIN;

    for (int i = 0; i < LEN+1; i++) 
        ls[i] = LEN;
    
    for (int i = 0; i < LEN; i++)
        adjust(i, arr);
}
int main(int argc, char const *argv[])
{
    int arr[] = {12, 1, 6, 8};
    memcpy(buf,arr,LEN*sizeof(int));
    build(buf);

    printf("%d\n", buf[ls[0]]); // 输出最小值

    arr[1] = 22; // 取出最小值1后，此处变为22
    memcpy(buf,arr,LEN*sizeof(int));
    adjust(1, buf); // 调整败者树
    printf("%d\n", buf[ls[0]]); // 输出最小值
    return 0;
}

结果输出：

1
2
1
6

败者树一般用于外部排序中，相关代码可访问ExternalSort