1 概述
 
竞赛树分为赢者树和输者树，赢者树更直观，输者树实现更高效。
比赛用二叉树来描述，每个外部节点表示一名选手，每个内部节点表示一场比赛，同一层内部节点代表一轮比赛，可以同时进行。
 
 如果竞赛树是完全二叉树，则对于n个选手的比赛，最少的比赛场次为$lo{g}_{2}n$。
竞赛树不全是完全二叉树，但是完全二叉树可以是比赛的次数最少，竞赛树也成为选择树。
 
2 赢者树
 
2.1 定义
 （1）赢者树：有n个选手的赢者树是一个完全二叉树，有n个外部节点和n-1个内部节点，每个内部节点记录的是该节点比赛的赢者。
 分类：最大赢者树、最小赢者树（平局的时候左孩子选手获胜）
 优点：当一个选手分数改变时，修改竞赛树比较容易。
 2.2 抽象数据类型winnerTree
 假设：选手个数一定，初始化后不能增减选手。
 
 
 
选手本身并不是赢者树的组成部分，内部节点才是。
 
 
 
template<class T>
class winnerTree
{
public:
	virtual ~winnerTree() {}
	virtual void initialize(T* thePlayer, int theNumberOfPlayers) = 0;
	// create winner tree with thePlayer[1:numberOfPlayers]
	virtual int winner() const = 0;
	// return index of winner
	virtual void rePlay(int thePLayer) = 0;
	// replay matches following a change in thePLayer
};
 
2.3 赢者树的实现
 （1）表示
 
 n名选手，n-1个内部节点分别对应数组player[1: n]，tree[1: n-1]
 对于任何一个外部节点player[i]，其父节点tree[p]由以下公式给出：
 $$p=\{\begin{array}{rlrlrlr}(i+offset)/2& & & & & & i\le lowExt\\ (i-lowExt+n-1)/2& & & & & & i>lowExt\end{array}$$
 其中，$s=2^{|lo{g}_2(n-1)|}$、$offset=2\ast s-1$
 （2）初始化
 从右孩子开始，逐层往上，且每层从左往右依次考察右孩子选手。
 （3）类completeWinnerTree
 
template<class T>
class completeWinnerTree : public winnerTree<T>
{
public:
	completeWinnerTree(T* thePlayer, int theNumberOfPlayers)
	{
		tree = NULL;
		initialize(thePlayer, theNumberOfPlayers);
	}
	~completeWinnerTree() { delete[] tree; }
	void initialize(T*, int);
	int winner() const
	{
		return tree[1];
	}
	int winner(int i) const
	{
		return (i < numberOfPlayers) ? tree[i] : 0;
	}
	// return winner of match at node i
	void rePlay(int);
	void output() const;
private:
	int lowExt;           // lowest-level external nodes
	int offset;           // 2^log(n-1) - 1
	int* tree;            // array for winner tree
	int numberOfPlayers;
	T* player;            // array of players
	void play(int, int, int);
};
 
3 总结
 
最先适配法求解箱子问题
 相邻适配法求解箱子装载问题

一、竞赛树
 
         假设有n个选手参加一场网球比赛，比赛规则是“突然死亡法”，即只要输一场就会被淘汰。一对一进行比拼，最后只剩下一个选手保持不败。下图13-1中显示了比赛过程，有a~h一共8名选手。这个比赛使用二叉树进行表示，每一个外部节点表示一名选手，每一个内部节点表示一场比赛，该节点的孩子表示比赛的选手。在同一层的内部节点代表一轮比赛，可以同时进行。在第一轮比赛中，对阵的选手有ab之间、cd之间、ef之间以及gh之间。每一场比赛的胜利者被记录在代表该比赛的内部节点中。在下图a中，第一轮比赛的胜利者为b、d、e和h，其余四位选手直接淘汰；下一轮比赛的对阵是bd之间、eh之间，胜利者是b和e，并且进入决赛；最后胜利者是e，放在根节点上。整个比赛过程见图a所示。图b中给出5名选手参加的比赛，从a到e，最后的胜利者是c。
 
         
 
       上图的两颗树都是完全二叉树。现实中竞赛所对应的树不一定是完全二叉树，但是这样做会使得比赛的场次最少。而且上面的竞赛树每一个内部节点记录的是比赛的赢者，我们称之为赢者树。如果内部节点记录的是比赛的输者，我们称之为输者树。应用中赢者树更加直观，但是输者树的实现效率更高。
 
       我们定义赢者树：有n个选手的一颗赢者树是一颗完全二叉树，它有n个外部节点和n-1个内部节点，每一个内部节点记录的是在该节点进行比赛的胜利者。我们定义最小赢者树，每一场比赛分数少的选手获胜；最大赢者树中，每一场比赛分数多的选手获胜。在分数相等时，左孩纸表示的选手获胜。下图13-2中a是一颗有8名选手的最小赢者树，b是一颗有5名选手的最大赢者树。每一个外部节点下面的数字表示选手的分数。
 
        
 
二、赢者树
 
       我们使用完全二叉树的数组表示赢者树。一颗赢者树有n名选手，需要n-1个内部节点 tree[1:n-1]。选手或者外部节点用数组 player[1:n] 表示，因此 tree[i] 是数组player的一个索引，类型为int。在赢者树的节点 i 对应比赛中的赢者 tree[i] 。图13-4给出在5个选手的赢者树中，各节点与数组 tree 和 player 之间的对应关系。
 
       
 
      为实现这种对应关系，我们必须能够确定外部节点 player[i]  的父节点 tree[p]。当外部节点的个数为n时，内部节点的个数为n-1。最低层最左端的内部节点，其编号为s，并且有s=2^log（n-1）。因此，最底层内部节点的个数为n-s，而最底层外部节点的个数lowExt是这个数的2倍。例如，在图13-4中，n=5，s=4，最底层最左端的内部节点是 tree[4]，这一层的内部节点个数为n-4=1个。最底层外部节点个数lowExt=2，倒数第二层最左端的外部节点编号是lowExt+1.。令offset=2*s-1。对于任何一个外部节点 player[i] ，其父节点tree[p]有一下公式给出：
 
      
 
      赢者树关键的两个操作是初始化和重新组织比赛。为了初始化一个赢者树，我们从右孩纸选手开始，进行他所参加的比赛，而且逐层网上，只要是从右孩纸上升到比赛节点，就可以进行在该节点的比赛。为此，要从左往右的考察右孩纸选手。在图13-4的树种，我们首先进行选手 player[2] 的比赛，然后进行 player[3] 的比赛，最后进行 player[5]的比赛。首先，我们进行选手 player[2] 参加在节点 tree[4]  的比赛，但是接下来，我们不能在上一层节点 tree[2]  的比赛，因为 tree[4] 是左孩纸。然后我们进行选手 player[3] 参加在tree[2] 的比赛，但是接下来不能进行在节点tree[1]的比赛，因为tree[2]是左孩纸。最后我们进行选手 play[5] 参加的在节点tree[3]的比赛和在节点 tree[1] 的比赛。注意，节点 tree[i] 节点记录的是比赛的赢者。
 
      当选手 thePlayer 的值改变，在从外部节点 player[ thePlayer ] 到根节点 tree[1] 的路径上，一部分或者全部比赛都需要进行重赛。为简单起见，我们要路径上的全部比赛重赛。具体的实现方案如下：
 
三、赢者树的实现
 
 
#pragma once 
#include<iostream>

using namespace std;

template <class T>
class winnerTree
{
public:
	//构造函数和析构函数
	winnerTree(T* thePlayer, int theNumberOfPlayer)
	{
		tree = NULL;
		initializer(thePlayer, theNumberOfPlayer);
	}
	~winnerTree(){ delete[] tree; }

	//使用数组thePlayer初始化一个赢者树
	void initializer(T *, int );
	//返回比赛最后赢者的下标
	int winner() const { return tree[1]; }
	//返回比赛中某一环节的比赛的赢者
	int winner(int i) const { return (i < numberofPlayer) ? tree[i] : 0; }
	//因改变某一个player的值进而重赛
	void rePlay(int);
	//输出
	void output() const;

private:
	T* player;//参赛成员组成的数组
	int numberofPlayer;//参赛成员的数量
	int* tree;//赢者树，数组表示，赢者树只包含比赛结果，节点表示赢者的下标

	int lowExt;//用于生成赢者树，表示最底层外部节点的个数
	int offset;//用于生成赢者树，=2^log(n-1) - 1，详见解析
	void play(int, int, int);//初始化需要用到，
};

//使用数组thePlayer初始化为一个赢者树
template<class T>
void winnerTree<T>::initializer(T *thePlayer, int theNumberOfPlayers)
{
	int n = theNumberOfPlayers;
	if (n < 2)
	{
		cerr << "Must have at least 2 players"; exit(0);
	}

	player = thePlayer;
	numberofPlayer = n;
	delete[] tree;
	tree = new int[n];//n个外部节点，需要n-1内部节点，而数组0空置不用，所以需要n的空间

	int s;
	for (s = 1; 2 * s <= n - 1; s += s);//最底层最左端的内部节点编号s = 2^log (n-1),取log的下整
	lowExt = 2 * (n - s);//最底层外部节点个数=2*最底层内部节点个数，最底层内部节点个数n-s
	offset = 2 * s - 1;//令offset=2*s-1
	//对于任何一个外部节点player[i]，其父节点tree[p]满足：
	//当i<=lowExt时，p=(i+offset)/2;  当i>lowExt时，p=(i-lowExt+n-1)/2;
	
	int i;
	//对最底层的外部节点比赛，从2，4，6。。开始知道判断
	for (i = 2; i <= lowExt; i += 2)
		play((offset + i) / 2, i - 1, i);
	//处理剩余的外部节点
	if (n % 2 == 1)
	{//如果外部节点n为奇数，需要特殊处理
		play(n / 2, tree[n - 1], lowExt + 1);
		i = lowExt + 3;
	}
	else//如果外部节点n为偶数
		i = lowExt + 2;
	for (; i <= n; i += 2)
		play((i - lowExt + n - 1) / 2, i - 1, i);
}

//play操作，从最开始的底层进行比赛，直到完成所有比赛决胜出最后赢者
template<class T>
void winnerTree<T>::play(int p, int leftchild, int rightchild)
{//从tree[p]开始的比赛，一直往上冒泡，直至根节点
	tree[p] = (player[leftchild] <= player[rightchild]) ? leftchild : rightchild;
	while (p % 2 == 1 && p > 1)
	{//p作为右孩纸出现，才继续往上走，因为最开始play中也是由右孩纸判断的
		tree[p / 2] = (player[tree[p - 1]] <= player[tree[p]]) ? tree[p - 1] : tree[p];
		p /= 2;
	}
}

//当thePlayer的值改变时，需要重赛,我们可以打乱然后重新初始化，但一般不这么做
template<class T>
void winnerTree<T>::rePlay(int thePlayer)
{
	int n = this->numberofPlayer;
	if (thePlayer <= 0 || thePlayer > n)
	{
		cerr << "Player index is illegal"; exit(0);
	}
	int matchNode,leftchid,	rightchild;//下一个需要重赛的节点以及他的孩纸

	//找出第一个需要重赛的节点以及他的左右孩纸
	if (thePlayer <= lowExt)
	{
		matchNode = (offset + thePlayer) / 2;
		leftchid = 2 * matchNode - offset;
		rightchild = leftchid + 1;
	}
	else
	{
		matchNode = (thePlayer - lowExt + n - 1) / 2;
		if (2 * matchNode == n - 1)
		{
			leftchid = tree[2 * matchNode];
			rightchild = thePlayer;
		}
		else
		{
			leftchid = 2 * matchNode - n + 1 + lowExt;
			rightchild = leftchid + 1;
		}
	}
	tree[matchNode] = (player[leftchid] <= player[rightchild]) ? leftchid : rightchild;

	//第二个需要重赛的节点中的特殊情况，即包含内部和外部节点
	if (matchNode == n - 1 && n % 2 == 1)
	{
		matchNode /= 2;
		tree[matchNode] = (player[tree[n - 1]] <= player[lowExt + 1]) ? tree[n - 1] : lowExt + 1;
	}
	//剩余的需要重赛的节点处理
	matchNode /= 2;
	for (; matchNode >= 1; matchNode /= 2)
		tree[matchNode] = (player[tree[2 * matchNode]] <= player[tree[2 * matchNode + 1]]) ?
							tree[2 * matchNode] : tree[2 * matchNode + 1];
}

//输出
template<class T>
void winnerTree<T>::output() const
{
	cout << "number of players  = " << numberofPlayer
		<< " lowExt = " << lowExt
		<< " offset = " << offset << endl;
	cout << "complete winner tree pointers are" << endl;
	for (int i = 1; i < numberofPlayer; i++)
		cout << tree[i] << ' ';
	cout << endl;
}

    测试代码： 
 
 
#include <iostream>
#include "WinnerTree.h"
using namespace std;

struct player
{
	int id, key;

	operator int() const { return key; }
};

void main(void)
{
	int n;
	cout << "Enter number of players, >= 2" << endl;
	cin >> n;
	if (n < 2)
	{
		cout << "Bad input" << endl;
		exit(1);
	}


	player *thePlayer = new player[n + 1];

	cout << "Enter player values" << endl;
	for (int i = 1; i <= n; i++)
	{
		cin >> thePlayer[i].key;
		thePlayer[i].id = i;
	}

	winnerTree<player> *w =	new winnerTree<player>(thePlayer, n);
	cout << "The winner tree is" << endl;
	w->output();

	thePlayer[2].key = 0;
	w->rePlay(2);
	cout << "Changed player 2 to zero, new tree is" << endl;
	w->output();
}

 

 
 
四、输者树
 
       输者树的内部节点记录的是比赛的失败者，我们可以使用 tree[0] 来记录比赛最后的赢者。当一个赢者发生变化，使用输者树可以简化重新比赛的过程。但是，其他选手发生改变时，还是使用赢者树比较方便，毕竟赢者树在概念上更容易理解。因此，只有选手 player[i] 为前一次比赛的赢家时，对于函数 rePlay（i）采用输者树比赢者树执行效率高。

本文代码下载： 
  
方式1：公众号【多栖技术控小董】回复【3587】免费获取下载链接
方式2：CSDN下载链接：https://download.csdn.net/download/qq_41453285/12099281
方式3：Github下载链接（进入之后下载里面的completeWinnerTree.zip文件）：https://github.com/dongyusheng/Interview-algorithm/tree/master/c%2B%2BAlgorithms
一、竞赛树概述
 
竞赛树是完全二叉树（或满二叉树）
竞赛树可以用数组来表示，而且存储效率最高
竞赛树的基本操作是替换最大（或最小）元素。如果有n个元素，这个基本操作的用时为Θ(logn)。虽然也能用堆和左高树来表示也能用近似的时间(O(logn))完成这个操作，但是用来实现可预见的断接操作都不容易
当我们需要按指定的方式断开连接时，比如选择最先插入的元素，或选择左端元素（假定每个元素都有一个从左到右的名次），这时，竞赛树就成为我们要选择的数据结构
竞赛树也称为选择树
竞赛树一般分为：赢者树、输者树
二、赢者树概述
 
 
 
什么是赢者树？
 
 
假设有n个选手参加一次网球比赛。比赛规则是“突然死亡法”：一名选手只要输掉一场球，就被淘汰。一对一选手比较，最终只剩下一个选择保持不败。这个“辛存者”就是比赛赢者
下图显示了一次网球比赛： 
   
有8名选手参加，从a和h
这个比赛用二叉树来描述，每个外部节点表示一名选手，每个内部节点表示一场比赛（该节点的孩子表示比赛的选手）
在同一层的内部节点代表一轮比赛，可以同时进行
下图中，第一轮比赛中，对阵的选手有4对：a与b、c与d、e与f、g与h，第一轮比赛的赢者为b、d、e、h；下一轮比赛的对阵是b和d、e和h，并且进入决赛；最终赢者为e
 
 
 
下图也表示一场比赛，最终的赢者是c
 
 
 
赢者树概念：通过上面的演示案例我们可以知道，赢者树就是每一个内部节点所记录的都是比赛的赢者
有n个选手一棵赢者树是一棵完全二叉树，它有n个外部节点和n-1个内部节点，每个内部节点记录的是在该节点比赛的赢者
 
 
最大赢者树、最小赢者树（附：平局）
 
 
最大赢者树：分数大的选手获胜
最小赢者树：分数最小的选手获胜
不论是最大赢者树还是最小赢者树，当分数相等，平局的时候，左孩子表示的选手获胜
 
 
 
 
 
赢者树的初始化
 
 
n个选手的赢者树可以在Θ(n)时间内初始化
方法是： 
   
沿着从叶子到根的方向，在内部节点进行n-1场比赛
也可以采用后序遍历来初始化，每访问一个节点，就进行一场比赛
 
 
 
赢者树的重构
 
 
当一个节点的分数发生变化时，需要将赢者树进行重构
有一颗n个选手的赢者树中，当一个选手的分数发生变化时，需要修改的比赛场次介于之间，因此，赢者树的重构需耗时O()
 
 
 
赢者树的排序
 
 
步骤： 
   
我们假设对最小赢者树进行排序（那么最终的赢者就是关键字值最小的元素）
我们在所有的元素中选出关键字最小的元素，将该元素的关键字值改为最大值（假设为），使它赢不了剩余的其它任何选手
然后重构赢者树，这时的总冠军是排序在第二的元素。同样的道理，将该元素的关键字也改为最大值（假设为），使它也赢不了剩余的其它任何选手
依次类推，再一次重构赢者树......最终就可以完成n个元素的排序
复杂度： 
   
赢者树初始化的用时为Θ(n)。每次改变赢者的关键字并重构赢者树的用时为Θ()，因为在从一个外部节点到根的路径上，所有的比赛需要重赛。赢者树的重构共需n-1次。因此，整个排序过程的时间为Θ(n+)=Θ()
 
 
 
初始归并段的生成（外部排序）
 
 
目前为止，我们所讨论的排序方法（插入排序、堆排序等）都是内部排序法。这些方法要求待排序的元素全部放入一计算机内存。但是，当待排序的元素所需要的空间超出内存的容量时，内部排序法就需要频繁地访问外部存储介质（如磁盘），那里存储着部分或全部待排的元素。这使得排序效率大打折扣。于是我们需要引入外部排序法
 
外部排序一般包括两个步骤：
 
   
1.生成一些初始归并段（run），每一个初始归并段都是有序集
2.将这些初始归并段合并为一个归并段
 
演示案例
 
 
假设待排序的记录有16000个，使用内部排序一次最多可排序1000个记录
步骤如下： 
   
1.重复下面操作16次，得到16个初始归并段 
     
输入1000个记录
用内部排序法对这1000个记录排序
输出排序结果，即归并段
2.开始合并归并段：在这个步骤中，我们进行若干次归并。每一次归并都是将最多k个归并段合并为一个归并段，归并段耳朵个数也因此讲到归并前的1/k。这个过程持续到归并段的个数等于1为止
本例有16个初始归并段。它们的编号分别为R1、R2......R16： 
   
在第一次归并中，先将R1~R4合并为S1，其长度为4000个记录，然后将R5~R8合并，以此类推
在第二次归并中，将S1~S4合并为T1，它是外部排序的最终结果
 
 
 
合并归并段的方法解析
 
 
合并k个归并段的方法是： 
   
从k个输入归并段的前面，不断把关键字最小的元素移到正在生成的输出归并段
当所有元素从k个输入归并段移至输出归并段时，合并过程就完成了
注意：在选择输出归并段的下一个元素时，在内存中只需要知道每个输入归并段的首元素的关键字即可。因此，只要有足够的内存来保存k个关键字，就可以完成k个任意长度的归并段。但是在实际应用上，我们需要每一次能输入/输出很多元素，以减少输入/输出的次数
以上面的演示案例为例： 
   
在上列待排的16000个记录中，每个归并段有1000个记录，而内存容量也是1000个记录
为了合并前4个归并段，可将内存分为5个缓冲区，每个缓冲区的容量为200个记录。前4个为输入缓冲区，第5个为输出缓冲区
从前4个输入归并段各取200个记录放入4个输入缓冲区。把合并的记录放入输出缓冲区。不断把输入缓冲区合并后放入输出缓冲区，直到以下的一个条件满足为止： 
     
1.输出缓冲区已满
2.某一输入缓冲区变空
当第一个条件满足时，将输出缓冲区的记录写入磁盘，写完之后继续合并
当前两个条件满足时，从空缓冲区所对应的输入归并段继续读取记录，读取过程结束之后，继续合并
当4000个记录都写入一个归并段S1时，前4个归并段的合并过程结束
 
复杂度分析
 
 
在归并段合并中，决定时间的因素之一是在步骤1（“输出缓冲区已满”）中生成的初始归并段的个数。使用赢者树可以减少初始归并段的个数
假设一棵赢者树有p名选手，其中每个选手是输入集合的一个元素，它有一个关键字和一个归并段号
前p个元素的归并段号均为1
当两个选手进行比赛时，归并段号小的选手获胜；在归并段号相同时，关键字小的选手获胜
为生成初始归并段，重复地将总冠军W移动它的归并号所对应的归并段，并用下一次输入元素N取代W 
   
如果N的关键字大于等于W的关键字，则令元素N的归并段号与W的相同，因为在W之后把N输出到同一归并段不会影响归并段的持续
如果N的关键字小于W的关键字，则令元素N的归并号为W的归并段号加1，因为在W之后吧把N输出同一个归并段将破坏归并段的排序
 
初始归并段的长度
 
 
当采用上述方法生成初始归并段时，初始归并段的平均长度约为2p
当2p大于内存容量时，我们希望能得到更少的初始归并段（与上述方法相比）
事实上，倘若输入集合已经有序（或几乎有序），则只需生成最后的归并段，这样可以跳过归并段的合并，即步骤2（“某一输入缓冲区变空”）
 
 
 
k路合并
 
 
在k路合并（上面的初始归并段）中，k个归并段合并成一个归并段
按照上面所述的方法，每一个元素合并到输出归并段所需的时间为O(k)，因为每一次迭代都需要在k个关键字中找到最小值。因此，产生一个大小为n的归并段所需要的总时间为O(kn)
而使用赢者树可将这个时间缩短为Θ(k+nlogk)： 
   
首先用Θ(k)的时间初始化一棵有k个选手的赢者树，这k个选手分别是k个归并段的头元素
然后将赢者移入输出归并段，并从相应的输入归并段中取出下一个元素替代赢者的位置
若该输入段无下一个元素，则用一个关键字值很大（例如）的元素替代。这个提取和替代赢家的过程需要n次，一次需要时间为Θ(logk)
一次k路合并的总时间为Θ(k+nlogk)
 
三、竞赛树的抽象数据类型（ADT）
 
 
我们定义的抽象数据类型为WinnerTree
我们假设选手的个数是固定的。也就是说，如果初始化时的选手个数为n，那么初始化之后不能再增减选手
选手本身并不是赢者树的组成部分，组成赢者树的成分是内部节点
赢者树支持的操作有： 
  
初始化一棵具有n名选手的赢者树
返回赢者
重新组织从选手i到根的路径上的比赛
四、竞赛树的抽象类
 
根据抽象数据模型，我们定义了下面的抽象类
#include "main.h"

template<class T>
class winnerTree
{
public:
	virtual ~winnerTree() {}

	//用数组thePlayer[1:numberOfPlayers]生成赢者树
	virtual void initialize(T *thePlayer, int theNumberOfPlayers) = 0;

	//返回赢者的索引
	virtual int winner()const = 0;

	//在参赛者thePLayer的分数变化后重赛
	virtual void rePlay(int thePLayer) = 0;
};
 
五、赢者树的编码实现
 
 
 
赢者树的数组表示
 
 
假设用完全二叉树的数组来表示赢者树
一棵赢者树有n名选手，需要n-1个内部节点。选手用player数组来表示，赢者树节点用tree数组来表示
下图给出了在有5个选手的赢者树中，各节点与数组tree和player之间的对应关系
 
 
 
数组与索引的关系
 
 
为了实现上面的对应关系，我们必须能够确定外部节点player[i]的父节点tree[p]
当外部节点的个数为n时： 
   
内部节点的个数为n-1
最底层最左端的内部节点，其编号为s，且s=
因此，最底层内部节点的个数为n-s，最底层外部节点个数lowExt是这个数的2倍
例如，在上图中： 
   
n=5，s=4，最底层最左端的内部节点时tree[4]，这一层的内部节点个数为n-4=1个
最底层外部节点个数lowExt=2，倒数第2层最左端的外部节点号为lowExt+1
令offset=2*s-1，对于任何一个外部节点player[i]，其父节点tree[p]由以下公式给出：
 
 
 
 
 
赢者树的初始化
 
 
原理：为了初始化一棵赢者树，我们从右孩子选手开始，进行他所参数的比赛，而且逐层往上，只要是从右孩子上升到比赛节点，就可以进行在该节点的比赛。为此，要从左往右地考察右孩子选手
在下图中： 
   
在下面的步骤中，我们会依次进行选手player[2]参加的比赛，然后进行选手player[3]参加的比赛，最后进行选手player[5]参加的比赛
首先，我们进行选手player[2]参加的在节点tree[4]的比赛
但是接下来，我们不能进行在上一层节点tree[2]的比赛，因为tree[4]是它的左孩子
然后我们进行选手player[3]参加的在节点tree[2]的比赛，但是接下来不能进行在节点tree[1]的比赛，因为tree[2]是它的左孩子
最后我们进行选手player[5]参加的在节点tree[3]的比赛和在节点tree[1]的比赛
注意，当在节点tree[i]进行比赛时，参加该比赛的选手已经确定，而且选手的记录已经存储在节点tree[i]的子节点中
 
 
 
 
 
重新组织比赛
 
 
当选手thePlayer的值改变时，在从外部节点player[thePlayer]到根tree[1]的路径上，一部分或全部比赛都需要重赛
为简单起见，我们将该路径上的全部比赛进行重赛
实际上，在上面的例子中，改变的只是赢者的值
一个赢者的值改变了，必然会导致从赢者对应的外部节点到根的路径上的所有比赛要重赛
 
 
 
编码实现
 
 
下面我们实现一个最小赢者树
抽象类定义如下：
 
#ifndef WINNERTREE_H_

#include "main.h"

template<class T>
class winnerTree
{
public:
	virtual ~winnerTree() {}

	//用数组thePlayer[1:numberOfPlayers]生成赢者树
	virtual void initialize(T *thePlayer, int theNumberOfPlayers) = 0;

	//返回最终赢者的索引
	virtual int winner()const = 0;

	//在参赛者thePLayer的分数变化后重赛
	virtual void rePlay(int thePlayer) = 0;
};

#endif
 
 
赢者树定义： 
   
方法winner的时间复杂性是O(1)。initialize的时间复杂性为O(n)，rePlay的时间复杂性是O(logn)。其中n是竞赛选手个数
 
#ifndef COMPLETEWINNERTREE_H_

#include "main.h"
#include "myExceptions.h"
#include "winnerTree.h"

template<class T>
class completeWinnerTree :public winnerTree<T>
{
public:
	completeWinnerTree(T *thePlayer, int theNumerOfPlayers) {
		//构造函数，将赢者树初始化为空，然后生成赢者树
		this->tree = nullptr;
		initialize(thePlayer, theNumerOfPlayers);
	}
	~completeWinnerTree() {
		//析构函数
		if (tree) {
			delete[] tree;
		}
		tree = nullptr;
	}

	//用数组thePlayer[1:numberOfPlayers]生成赢者树
	void initialize(T *thePlayer, int theNumberOfPlayers)override;
	//返回最终赢者的索引
	int winner()const override { return this->tree[1]; }
	//返回竞赛树某个节点的赢者
	int winner(int i) const{
		return (i < this->numberOfPlayers) ? this->tree[i] : 0;
	}
	//在参赛者thePLayer的分数变化后重赛
	void rePlay(int thePlayer)override;

	//输出赢者树中的一些信息
	void output()const;
private:
	/*
		对tree[p]节点进行比赛，leftChild为左子节点，rightChild为右子节点
		如果还有父节点，继续向上比赛
	*/
	void play(int p, int leftChild, int rightChild);
private:
	int lowExt;         //最底层外部节点个数
	int offset;         //offset=2*s-1（s为最底层最左端的内部节点）
	int *tree;          //赢者树
	int numberOfPlayers;//竞赛选手的数量
	T *player;          //保存竞赛选手
};

//用数组thePlayer[1:numberOfPlayers]生成赢者树
template<class T>
void completeWinnerTree<T>::initialize(T *thePlayer, int theNumberOfPlayers)
{
	int n = theNumberOfPlayers;//竞赛者的数量
	if (n < 2)//如果竞赛者的数目小于2，不能进行竞赛
		throw illegalParameterValue("must have at least 2 players");

	//初始化类内数据成员
	this->player = thePlayer; //竞赛者
	this->numberOfPlayers = n;//当前竞赛者的数目
	delete[] this->tree;      //删除竞赛树
	this->tree = new int[n];        //创建竞赛树数组
	
	//计算s=2^log (n-1)
	int i, s;
	for (s = 1; 2 * s <= n - 1; s += s);

	this->lowExt = 2 * (n - s);//最底层外部节点个数（见公式）
	this->offset = 2 * s - 1;//固定值（见公式）

	//为最低级别的外部节点进行匹配
	for (i = 2; i <= this->lowExt; i += 2)
		play((this->offset + i) / 2, i - 1, i);

	//处理剩余的外部节点
	if (n % 2 == 1) {
		//特殊情况下奇数n，发挥内部和外部节点
		play(n / 2, this->tree[n - 1], this->lowExt + 1);
		i = this->lowExt + 3;
	}
	else {
		i = this->lowExt + 2;
	}

	//i是最左边剩余的外部节点
	for (; i <= n; i += 2)
		play((i - this->lowExt + n - 1) / 2, i - 1, i);
}

/*
	对tree[p]节点进行比赛，leftChild为左子节点，rightChild为右子节点
	如果还有父节点，继续向上比赛
*/
template<class T>
void completeWinnerTree<T>::play(int p, int leftChild, int rightChild)
{
	//因为为最小赢者树，所以返回值比较小的为赢者
	this->tree[p] = (this->player[leftChild] <= this->player[rightChild]) ? 
		leftChild : rightChild;

	//如果是右子节点并且还有父节点，那么就继续向上进行比赛
	while ((p % 2 == 1) && (p > 1)) {
		//对父节点进行比赛
		this->tree[p / 2] = (this->player[tree[p - 1]] <= this->player[tree[p]]) ? 
			tree[p - 1] : tree[p];
		p /= 2;//移至父节点
	}
}

//在参赛者thePLayer的分数变化后重赛
template<class T>
void completeWinnerTree<T>::rePlay(int thePlayer)
{
	int n = numberOfPlayers;//竞赛者的数量
	if (thePlayer <= 0 || thePlayer > n)
		throw illegalParameterValue("Player index is illegal");

	int matchNode,       // 将在其中进行下一场比赛的节点
		leftChild,       // 比赛节点的左孩子
		rightChild;      // 比赛节点的右孩子

	// 查找第一个匹配节点及其子节点
	if (thePlayer <= lowExt)
	{//从最低层次开始
		matchNode = (offset + thePlayer) / 2;
		leftChild = 2 * matchNode - offset;
		rightChild = leftChild + 1;
	}
	else
	{
		matchNode = (thePlayer - lowExt + n - 1) / 2;
		if (2 * matchNode == n - 1)
		{
			leftChild = tree[2 * matchNode];
			rightChild = thePlayer;
		}
		else
		{
			leftChild = 2 * matchNode - n + 1 + lowExt;
			rightChild = leftChild + 1;
		}
	}

	tree[matchNode] = (player[leftChild] <= player[rightChild])
		? leftChild : rightChild;

	// 第二次比赛的特殊情况
	if (matchNode == n - 1 && n % 2 == 1)
	{
		matchNode /= 2;   // 移至父节点
		tree[matchNode] = (player[tree[n - 1]] <=
			player[lowExt + 1]) ?
			tree[n - 1] : lowExt + 1;
	}

	// 玩剩下的比赛
	matchNode /= 2;  // 移至父节点
	for (; matchNode >= 1; matchNode /= 2)
		tree[matchNode] = (player[tree[2 * matchNode]] <=
			player[tree[2 * matchNode + 1]]) ?
		tree[2 * matchNode] : tree[2 * matchNode + 1];
}

//输出赢者树中的一些信息
template<class T>
void completeWinnerTree<T>::output()const
{
	std::cout << "number of players  = " << this->numberOfPlayers
		<< " lowExt = " << this->lowExt
		<< " offset = " << this->offset << std::endl;

	//输出每一个节点的赢者
	std::cout << "complete winner tree pointers are" << std::endl;
	for (int i = 1; i < this->numberOfPlayers; i++)
		std::cout << this->tree[i] << ' ';
	std::cout << std::endl;
}
#endif
 
 
主函数定义：
 
struct player
{
	int id, key;

	operator int() const { return key; }
};

int main()
{
	//输入竞赛者的数量
	int n;
	std::cout << "Enter number of players, >= 2" << std::endl;
	std::cin >> n;
	if (n < 2){
		std::cout << "Bad input" << std::endl;
		exit(1);
	}

	//创建竞赛者数组
	player *thePlayer = new player[n+1];
	
	std::cout << "Create players success" << std::endl;

	//输入每一个竞赛者的键值
	std::cout << "Enter player values" << std::endl;
	for (int i = 1; i <= 10; i++)
	{
		std::cin >> thePlayer[i].key;
		thePlayer[i].id = i;
	}
	
	//创建一个赢者树
	completeWinnerTree<player> *w = new completeWinnerTree<player>(thePlayer, n);

	std::cout << "Create completeWinnerTree success" << std::endl;

	//输出最终的赢者
	std::cout << "The winner tree is" << std::endl;
	w->output();

	//改变一个节点的值，然后重新进行比赛
	thePlayer[2].key = 0;
	w->rePlay(2);
	std::cout << "Changed player 2 to zero, new tree is" << std::endl;
	w->output();

	//改变一个节点的值，然后重新进行比赛
	thePlayer[3].key = -1;
	w->rePlay(3);
	std::cout << "Changed player 3 to -1, new tree is" << std::endl;
	w->output();

	//改变一个节点的值，然后重新进行比赛
	thePlayer[7].key = 2;
	w->rePlay(7);
	std::cout << "Changed player 7 to 2, new tree is" << std::endl;
	w->output();

	return 0;
}
 
 
 
 
六、输者树
 
考察在赢者树中的rePlay操作。在许多应用中，只有在一个新选手替代了前一个赢者之后，才执行这个操作。这是，在从赢者的外部节点到根节点的路径上，所有比赛都要重新进行
考察下图的最小赢者树： 
  
假设赢者f被关键字为5的选手f'取代
重新进行的第一场比赛时在e和f'之间进行，并且f'获胜，e在以前与f的比赛中是输者
赢者f'在内部节点tree[3]的比赛中与g对阵，注意g在tree[3]处于f的前一场比赛中是输者，现在g与tree[3]处f'对阵是赢者
接下来，g在根节点的比赛中与a对阵，而a在根节点处的上一场比赛中是输者
 
 
 
如果每个内部节点记录的是在该节点比赛的输者而不是赢者，那么当赢者player[i]改变后，在从该节点到根的路径上，重新确定每一场比赛的选手所需要的操作量就可以减少。最终的赢者科技路在tree[0]中
下图a与图b相对应的输者树，它有8名选手。当赢者f的关键字编程5时，我们移动带它的父节点tree[6]进行比赛，比赛的选手是player[tree[6]]和player[6]
也就是说，为确定选手f'=player[6]的对手，只需简单地查看tree[6]即可，而在赢者树中，还需要查看tree[6]的其它子节点
在tree[6]的比赛完成后，输者e被记录在此节点，f'继续在tree[3]比赛，对手是前一场的输者g，而g就记录在tree[3]中
这次的输者是fg'，它被记录于tree[3]
赢者g则继续在tree[1]比赛，对手是上一场比赛的输者a，而a就记录在tree[1]。这次的输者是g，它被记录在tree[1]。新的输者树如下图b所示
 
 
 
当一个赢者发生变化时，使用输者树可以简化重赛的过程，但是，当其他选手发生变化时，就不是那么回事了。例如，当选手d的关键字由9变成3时，在tree[5]、tree[2]和tree[1]上的比赛将重新进行。在tree[5]的比赛中，d的对手是c，但c不是上一场比赛的输者，因此它没有记录在tree[5]中。在tree[2]的比赛中，d的对手是a，但a也不是上一场比赛的输者。在tree[1]的比赛中，d的对手是f'，但f同样不是上一场比赛的输者。为了重新进行这些比赛，还得用到赢者树。因此，仅当player[i]为前次比赛的赢家时，对于函数rePlay(i)，采用输者树比采用赢者树执行效率更高

竞赛树
 
竞赛树的基本操作是替换最大（或最小）元素。如果有n个元素，这个基本操作的用时为O(logn).。虽然用堆和左高树来表示也能用近似的时间（O(logn)）完成这个操作，但是用来实现可预见的断连操作都不容易。当我们需要按指定的方式断开连接时，比如选择最先插入的元素，或选择左端元素（假定每个元素都有一个从左到右的名次），这时，竞赛树就成为我们要选择的数据结构。