数据结构:败者树

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

败者树的中间结点记录的败者的标号

它可以在 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

文章作者: Sshpark
文章链接: http://sshpark.com.cn/2018/11/22/数据结构:败者树/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Sshpark