树排 胜者树 败者树

缘起

闲来无事，研究一下排序中的树形排序（简称树排）这种排序思想.

分析

树排，全称是树形选择排序, 因为其排序的过程和体育比赛中的8进4,4进2,2争冠非常相似， 所以树排又称为锦标赛排序. 而且树排中用到的树就是胜者树（因为是8进4、4进2、2争冠嘛~ 当然是胜者啦~）

算法的时间复杂度是O(NlogN).所用的树是满二叉树,不足的元素用inf补足
因为只是相邻的比较,所以树形选择排序是稳定排序.

下图可以视作是树排的过程.

​ 图1

参与排序的数组是

1
49, 38, 65, 97, 76, 13, 27, 49

比赛的过程全程淘汰赛. 伊始,两两配对捉对厮杀. 小的胜出. 所以得到第一轮的胜者

1
38,65,13,27

然后再进行一轮捉对厮杀, 小的胜出, 得到第二轮的胜者

1
38,13

最后争冠, 小的胜出，得到冠军是13. 然后冠军出堆（没错~ 树排和堆排极为相似的）. 然后找到13这个冠军所在的索引, 然后一路更新到根节点，这一路上的胜者的索引都要变化. 如此往复, 直至所有的数组元素都出堆.

所以树排算法很简单

  1. 建树（建成上图的第一幅中的样子，即决出第一轮冠军的样子），注意，胜者树中的节点上都是原数组中的索引,而不是真实值. 因为第二步要拿到冠军的索引,然后一路向上（siftUp）更新胜者树.
  2. 冠军出堆，然后找到冠军的索引, 将此索引处的值变成inf（因为要求最小嘛~）,进行siftUp调整. 剩余元素个数-1

重复上述步骤直至剩余元素个数为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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include "stdafx.h"

#include <stdio.h>
#include <algorithm>
using namespace std;
#define LOCAL

const int maxn = 100, inf = 0x3f3f3f3f;
int a[9] = {-1, 7,49,38, 65 ,97, 76, 13, 27}; // 参与排序的数组, 0索引不用于存储数据

struct SegTreeNode
{
	int begin, end, val;
}segTree[maxn<<2];

void build(int begin, int end, int i)
{
	segTree[i].begin = begin, segTree[i].end = end;
	if (begin ==end)
	{
		segTree[i].val = begin; // 胜（线）者（段）树中存储的是索引，而不是值本身, 不然不利于updata
		return;
	}
	int mid = (begin+end)>>1;
	build(begin, mid, i<<1);
	build(mid+1, end, i<<1|1);
	segTree[i].val = a[segTree[i<<1].val]<a[segTree[i<<1|1].val]?segTree[i<<1].val:segTree[(i<<1|1)].val; // 胜者为王!
}

void updata(int begin, int end, int i)
{
	if (begin==segTree[i].begin && end==segTree[i].end)
	{
		return;
	}
	int mid = (segTree[i].begin+segTree[i].end)>>1;
	if (end<=mid)
	{
		updata(begin, end, i<<1);
	}
	else if (begin>mid)
	{
		updata(begin, end, i<<1|1);
	}
	else // 实际上因为是单点更新（begin=end），其实并不会野马分鬃~
	{
		updata(begin, mid, i<<1);
		updata(mid+1, end, i<<1|1); // 野马分鬃!
	}
	segTree[i].val = a[segTree[i<<1].val]<a[segTree[i<<1|1].val]?segTree[i<<1].val:segTree[(i<<1|1)].val;
}

void treesort(int a[], int n) // 对 a[1,...,n]进行树排
{
	build(1,n,1);
	while(n--)
	{
		printf("%d ", a[segTree[1].val]);
		a[segTree[1].val] = inf;
		updata(segTree[1].val, segTree[1].val, 1); // 其实是单点更新线段树,可以像上面updata递归, 也可以直接while(不是根节点){...}这样非递归的写法, 我采用的是线段树的标准写法——递归
	}
}

int main() {

#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	treesort(a, 8);
	return 0;
}

对的，你没看错~ 其实胜者树就是线段树. 你想想看就知道了. 区间更新（其实是单点更新）,区间（即线段树上的节点）维护的是该区间上的最小值对应的原数组的索引.

至此，胜者树和树排我们讲清楚了. 下面讲讲败者树.

胜（线）者（段）树在内部排序有用. 而败者树在外部排序的多路平衡归并中有用武之地. 怎么说呢?

首先，内部排序和外部排序的概念就不消多说了. 这在严蔚敏奶奶的书的第11章讲的很清楚了. 一言以蔽之就是参与排序的数字如果全部在内存中的话，则就是内部排序，反之，如果有部分在外存储器上（如顺序存储设备——磁带或者直接存储设备——磁盘）则就是外部排序.

在信息爆炸的年代，海量数据大文件排序是很普遍的

外部排序基本上由2个相对独立的阶段组成. 首先，按照可用内存的大小将外存上的含有n个记录的文件分成若干长度为l的子文件或者段（segment）. 依次读入内存并利用内部排序的算法（所以，外排序其实本质上在真正排序的时候用的还是内排序的算法，毕竟CPU不能直接和外存打交道的,只能直接和内存打交道）对他们进行排序。并将排序后的有序内容重新写入外存成为有序子文件. 这种有序子文件称为归并段. 然后逐趟归并，使得归并段不断增大. 直至整个文件有序为止. 关于内排序阶段已经写过很多文章论述了. 这里就不赘述了.外部排序比内排序在同等算法下要慢的多，根本原因在于IO时间相比内存和cpu交互运算时间太长. 所以所谓外部排序的算法主要集中的地方在于如何有效降低归并的趟数.

这么干说并不好理解，举个例子吧

1
2
3
含有10000个记录的文件，假设内存只能支持1000条记录的内部排序. 则首先通过10趟内部排序得到10个初始
归并段 R1~R10. 其中每个归并段都含有1000条记录. 然后进行如下图所示的两两归并. 直至得到一个有序文件
为止.

​ 图2

从上图可见，10个初始归并段归并到最终的有序文件，共进行了4趟归并. 上图称为2路平衡归并(所谓平衡指的是参与归并的两路归并段的元素个数的比值是O(1)). 而一般情况下

1
m个初始归并段进行k路平衡归并时, 归(I)并(O)的趟数是 O(log_{k}m)

这么看就显然了——若能增加归并的路数k, 就能有效降低归并的趟数, 于是这就是所谓的多路平衡归并.

但是有人马上就会指出问题了——增加平衡归并的路数降低IO次数是没错，但是增加了内部排序的时间啊~ 这是一个矛盾的存在~ 怎么解决呢? 败者树横空出世——败者树使得内部排序的时间是一个与归并路数无关的数

这就能通过增加归并路数有效降低了外部排序的时间了.

怎么说呢? 为什么如果按照上图那样裸归并的话内部排序的时间会随着归并路数的增多而增加? 因为k个归并段，一共u个元素, 则要归并为u个元素的一个归并段. 回忆归并排序，每次决出最小的元素就要进行k-1次排序, 所以最后决出u个元素差不多要 (k-1)*u次运算. 所以一趟归并差不多是 O(k*n)数量级的运算（n是外部文件总的元素个数）.而总共经过log_{k}m*k*n数量级的运算. 换底公式变为
$$
\frac{log_{2}m}{log_{2}k}kn
$$
m是最初的归并段个数（和n成正比）. 所以$\frac{k}{log_{2}k}$ 将随着k增加而增加. 所以增大归并路数的话, 会增加内部排序的时间甚至抵消因为减少IO次数而带来的增益. 考虑上述算法的瓶颈——就是每次决出最小值需要O(k)是令人怀疑的. 真的需要O(k)时间吗? 如果有一种数据结构能让这个时间降低为O($log_{2}k$)的话，则我们惊喜的发现，内部排序的总耗时就变成了
$$
nlog_{2}m
$$
一个与归并路数无关仅仅与文件记录数量有关的常量. 所以增加归并路数是可以有效降低排序总时长的（但是注意，实际运用中k也不是越大越好的, 理论要根据实际进行调整）. 而败者树这种数据结构做到的事情就是将O(k)降低为了O($log_2{k}$)

好了，瞎比比那么多败者树的缘起以及作用. 下面看看败者树的运行过程

​ 图3

图3的第一幅是败者树的建树. ls[0],ls[1],ls[2],ls[3],ls[4]是败者树的内部节点（即非叶子节点）.b0~b4是败者树的叶子节点. 败者树的每个节点存储的都是两两比较的败者（数大者败，因为我每次要求出的是各归并路中的最小嘛~）在原数组中的索引. 具体说来

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

然后b3变成原b3所在一路的后一个元素13（其实就好比是胜者树中置为inf，所以下面败者树的实现代码中并没有多路归并，而是一样做的是数组排序，但是读者要知道, 其实做的事情和实线多路归并本质是一样的）. 则

  1. b3和它的父节点ls[4]比较, b3>b[ls[4]]=b[4], 所以b3败, 所以ls[4]更新为3. b4晋级下一轮.
  2. b4和它的父节点ls[2]比较, b4>b[ls[2]]=b[0], 所以b4败, 所以ls[2]更新为4, 胜者是0, b0晋级下一轮
  3. b0和它的父节点ls[1]比较, b0>b[ls[1]]=b[1], 所以b0败, 所以ls[1]更新为0, 最终胜者是1, 即ls[0]=1,算法输出 b[1]（原数组中次小）

注意，败者树调整的时候，只需要和它的父节点比较，而不需要像胜者树那样和它的兄弟节点比较. 因为节点记录的都是败者，而父节点记录的就是败者，所以只需要和父节点比较尝试去更新败者即可. 

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include "stdafx.h"

#include <stdio.h>
#include <algorithm>
using namespace std;
#define LOCAL

const int maxn = 100, inf = 0x3f3f3f3f;
int a[9] = {-1, 7,49,38, 65 ,97, 76, 13, 27}; // 参与排序的数组, 0索引不用于存储数据

struct SegTreeNode
{
	int begin,end,val; // val记录的是败者索引
}segTree[maxn<<2]; // 0索引不用

int build(int begin, int end, int i) // 返回的是以segTree[i]为根的子树的胜者编号，即每次递归做的事情其实是记录败者、返回胜者
{
	segTree[i].begin = begin, segTree[i].end = end;
	if (begin==end)
	{
		return segTree[i].val = begin; // 单点既是胜者又是败者,所以既记录又返回
	}
	int mid = (begin+end)>>1;
	int lwin = build(begin, mid, i<<1); // 左边的胜者
	int rwin = build(mid+1, end, i<<1|1); // 右边的胜者
	segTree[i].val = a[lwin] > a[rwin]?lwin:rwin; // 但是节点只记录败者(数大者为败)
	return lwin+rwin-segTree[i].val; // 返回胜者
}

int updata(int begin, int end, int i) // 返回胜者索引
{
	if (segTree[i].begin==begin && segTree[i].end == end)
	{
		return segTree[i].val = begin;
	}
	int mid = (segTree[i].begin+segTree[i].end)>>1, win;
	if (end<=mid)
	{
		win = updata(begin, end, i<<1);
	}
	else if (begin>mid)
	{
		win = updata(begin, end, i<<1|1);
	} // 因为是单点(begin=end), 不可能出现mid介于[begin,end]之间的情况,这体现了更新时败者树不需要与兄弟节点而只需要和父节点比较的特点
	if (a[segTree[i].val]>a[win]) // 如果败者依旧是当前节点的话,则当前节点不必变动,直接送win晋级即可
	{
		return win;
	}
	int ans = segTree[i].val; // 否则要变动了
	segTree[i].val = win; // 更新当前节点
	return ans; // 返回胜者
}

void loserSort(int a[], int n) // 对 a[1,...,n]进行败者树排序
{
	int win = build(1,n,1); // 建树
	while(n--)
	{
		printf("%d ", a[win]);
		a[win] = inf;
		win = updata(win, win,1);
	}
}

int main() {

#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	loserSort(a,8);
	return 0;
}

比较胜者树和败者树的代码，发现非常相似, 都是基于线段树实现——都像是一根根水管一样不断的将数组中的水（即数组元素）耗费O($log_2k$)时间吸取上来然后吐出来. 唯一的区别在于胜者树节点保存的是胜者.而败者树节点保存的是败者返回的是败者. 但是败者树更新起来只需要与父节点比较，所以较胜者树简单. 所以实践中使用败者树实现多路平衡归并. 而并不是说胜者树不能以相同效率实现多路平衡归并.

胜者树和败者树都能以O(logn)效率实现多路平衡归并. 只是败者树的常数更小一些.