问题描述

应用竞赛树结构模拟实现外排序。

基本要求

（1） 设计实现最小输者树结构ADT，ADT中应包括初始化、返回赢者，重构等基本操作。
（2） 设计实现外排序，外部排序中的生成最初归并串以及K路归并都应用最小输者树结构实现；
（3） 随机创建一个较长的文件；设计归并路数以及缓冲区的大小；获得外排序的访问磁盘的次数并进行分析。可采用小文件来模拟磁盘块。

解题

输者树介绍

对于输者树的构建过程，数据结构课本上并没有多说，仅仅讲解了赢者树，如下图所示，赢者上升进入下一次比赛。

哦，原来这就是赢者树，那么这个最小赢者树是不是就是最大输者树了呢？

想多了，课本上有一个最小输者树的图如下图所示：

说实话，第一次见到这个图我是一脸懵逼的(可能我当时上课讲的忘了)，中间结点加上上面的输者结点，包含$a\sim f$的所有结点，根本就不是我开始想象的输者树就是每个结点记录当前的输者。

后来在网上看了一些博客才懂什么意思，我们下面看一下课本上这个图是怎么建立起来的：

这棵树上，边的值才是比赛晋级的选手，而不是赢者树中结点的才是晋级。

我们按照先从右孩子开始的顺序来构建这棵最小输者树。

1. a与b比较，b输，a晋级
2. c与d比较，d输，c晋级
3. e与f比较，e输，f晋级
4. g与h比较，h输，g晋级
5. a与c比较，c输，a晋级
6. f与g比较，g输，f晋级
7. a与f比较，a输，f晋级

所以说，每个结点都保存了当前的输者没有错，只是图上没有表现出来晋级的选手而已。每次比赛的选手都是晋级的选手（我就说嘛，什么比赛最后要输的一方）。

外排序

这个外排序的思路是先利用内排序构造顺串，然后这些顺串在进行k路归并，合并成最终结果。

我们在这里使用最小输者树来构造顺串，这样可以减少初始顺串的个数。

在利用最小输者树构造顺串的时候，每个选手都对应着输入集合中的一个元素。另外，每一个选手还有一个顺串号。

赢者的规则是：

1. 具有较小顺串号的元素获胜。
2. 顺串号相同，较小元素值的元素获胜。

那这些元素的顺串号又怎么确定呢？伪代码如下：

建立前p个选手的最小赢者树（p是内存的大小）
while(还有元素没有输出到对应的顺串中)
{
	将最终赢者w移入它的顺串号所对应的顺串中;
	if(输入集合中又下一个元素)
		n=下一个元素;
	else {
		n=INT_MIN;
		n的顺串号=INT_MAX；//这样就不会输入顺串中
	}
	if(n的元素值>=w的值) n的顺串号=w的顺串号;
	else n的顺串号=w的顺串号+1;
	n代替w的位置，重构赢者树;
}

建立了这些顺串后，再利用一次最小输者树就可以将他们归并，并且存到对应的磁盘文件中。

完整代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <climits>
#include <algorithm>
#include <queue>
#include <vector>
#include <fstream>
#include <ctime>
#include <random>
using namespace std;


struct Variable//变量结构体
{
    Variable(){
        visitDiskTime=0;
        n=0; m=0;
        numberOfDisk=0;
    }
    string path;//磁盘的位置，可以根据自己的电脑修改
    string fileName="Disk.txt";//磁盘文件名称
    string file;//最终完整路径
    int visitDiskTime,n,m,numberOfDisk;
    char ch1,ch;
};
struct SequentialStringPlayer//用于构建顺串
{
    int id,key;
    bool operator<=(SequentialStringPlayer &p){
        return (id!=p.id) ? (id<p.id) : (key<p.key);
    }
};
template <class T>
class loserTree
{
public:
    virtual ~loserTree(){}
    virtual void initialize(T* thePlayer,int number)=0;
    virtual int getTheWinner() const =0;
    virtual void rePlay(int thePLayer,T newvalue)=0;
};
template <class T>
class MinimumLoserTree : public loserTree<T>
{
public:
    MinimumLoserTree(T* thePlayer=nullptr,int theNumberOfPlayers=0){
        tree=nullptr; advance=nullptr;
        initialize(thePlayer,theNumberOfPlayers);
    }
    ~MinimumLoserTree(){delete[] tree;delete[] advance;}
    void initialize(T* thePlayer,int theNumberOfPlayers);//初始化
    int getTheWinner() const {return tree[0];};//输出当前的赢者
    void rePlay(int thePlayer,T newvalue);//重构
private:
    int numberOfPlayers;
    int* tree;//记录内部结点，tree[0]是最终的赢者下标，不使用二叉树结点，因为父子关系都是通过计算得出
    int* advance;//记录比赛晋级的成员
    T* player;//参与比赛的元素
    int lowExt;//最底层外部结点的个数,2*(n-s)
    int offset;//2*s-1
    void play(int,int,int);
    int winner(int x,int y){return player[x]<=player[y]?x:y;};//返回更小的元素下标
    int loser(int x,int y){return player[x]<=player[y]?y:x;};//返回更大的元素下标
};
template <class T>
void MinimumLoserTree<T>::initialize(T* thePlayer,int theNumberOfPlayers)
{
    int n=theNumberOfPlayers;
    if(n<2) {
        cout<<"Error! the number must >= 2"<<endl;
        return;
    }
    player=thePlayer;
    numberOfPlayers=n;
    delete[] tree; delete[] advance;
    tree=new int[n+1];
    advance=new int[n+1];

    int s; for (s=1; 2*s<=n-1; s+=s);//s=2^log(n-1)-1（常数优化速度更快），s是最底层最左端的内部结点

    lowExt=2*(n-s); offset=2*s-1;

    for (int i=2; i<=lowExt; i+=2)//最下面一层开始比赛
        play((i+offset)/2,i-1,i);//父结点计算公式第一条

    int temp=0;
    if(n%2==1){//如果有奇数个结点，处理下面晋级的一个和这个单独的结点
        play(n/2,advance[n-1],lowExt+1);
        temp=lowExt+3;
    }
    else temp=lowExt+2;//偶数个结点，直接处理次下层

    for (int i=temp; i<=n; i+=2)//经过这个循环，所有的外部结点都处理完毕
        play((i-lowExt+n-1)/2,i-1,i);

    tree[0]=advance[1];//tree[0]是最终的赢者，也就是决赛的晋级者

}
template <class T>
void MinimumLoserTree<T>::play(int p, int leftChild, int rightChild)
{
    //tree结点存储相对较大的值，也就是这场比赛的输者
    tree[p]=loser(leftChild,rightChild);
    //advance结点存储相对较小的值，也就是这场比赛的晋级者
    advance[p]=winner(leftChild,rightChild);

    while(p % 2 == 1 && p > 1){
        tree[p/2]=loser(advance[p-1],advance[p]);
        advance[p/2]=winner(advance[p-1],advance[p]);
        p /= 2;//向上搜索
    }
}
template <class T>
void MinimumLoserTree<T>::rePlay(int thePlayer,T newvalue)
{
    int n=numberOfPlayers;
    if(thePlayer <= 0 || thePlayer > n){
        cout<<"Error! the number must >0 & <=n"<<endl;
        return;
    }

    player[thePlayer]=newvalue;

    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=advance[2*matchNode];
            rightChild=thePlayer;
        }
        else{
            leftChild=2*matchNode-n+1+lowExt;//这个操作是因为上面matchNode计算中/2取整了
            rightChild=leftChild+1;
        }
    }
    //到目前位置，我们已经确定了要比赛的场次以及比赛的选手

    //下面进行比赛重构，也就是和赢者树最大的不同，分两种情况
    if(thePlayer==tree[0]){//当你要重构的点是上一场比赛的赢家的话，过程比赢者树要简化
        for (; matchNode>=1; matchNode/=2){
            int oldLoserNode=tree[matchNode];//上一场比赛的输者
            tree[matchNode]=loser(oldLoserNode,thePlayer);
            advance[matchNode]=winner(oldLoserNode,thePlayer);
            thePlayer=advance[matchNode];
        }
    }
    else {//其他情况重构和赢者树相同
        tree[matchNode]=loser(leftChild,rightChild);
        advance[matchNode]=winner(leftChild,rightChild);
        if(matchNode==n-1 && n%2==1){//特殊情况，比赛结点是最后一层的最后一场比赛
            //特殊在matchNode/2后，左儿子是晋级的选手，右儿子是一场都没有比过赛的选手
            matchNode/=2;
            tree[matchNode]=loser(advance[n-1],lowExt+1);
            advance[matchNode]=winner(advance[n-1],lowExt+1);
        }
        matchNode/=2;
        for (; matchNode>=1; matchNode/=2){
            tree[matchNode]=loser(advance[matchNode*2],advance[matchNode*2+1]);
            advance[matchNode]=winner(advance[matchNode*2],advance[matchNode*2+1]);
        }
    }
    tree[0]=advance[1];//最终胜者
}
void init(Variable &va)
{
    cout<<"请输入您想要的模拟磁盘位置，接下来的操作都是在当前路径下进行，输入样例：/Users/longzhengtian/Desktop/text/"<<endl;
    cout<<"请输入："; cin>>va.path; va.file=va.path+va.fileName;
    cout<<"请输入您想要在磁盘中初始化数字的个数，这些数字将用于模拟外排序过程："; cin>>va.n;
    cout<<"请输入缓冲区大小（此处为缓冲区能存储数字的个数）："; cin>>va.m;
    cout<<"请问您是否想要将原始数据，顺串，最终数据显示在控制台中('y' or 'n')："; cin>>va.ch1; cout<<endl;

    ofstream fout1(va.file);
    if(!fout1.is_open()){
        cout<<"无法打开指定磁盘文件，无法初始化磁盘"<<endl;
        exit(0);
    }
    if(va.ch1=='y') cout<<"原始磁盘文件有："<<endl;
    for (int i=1; i<=va.n; i++){
        int x=random()%1000+1;
        fout1<<x<<' ';//random是C++11标准
        if(va.ch1=='y') cout<<x<<' ';
    }
    if(va.ch1=='y') cout<<endl<<endl;
    fout1.close();
}
void SequentialStringConstruction(Variable &va,SequentialStringPlayer* ssplayer)
{
    ifstream fin1(va.file);
    if(!fin1.is_open()){
        cout<<"无法打开指定磁盘文件，无法进行顺串构造"<<endl;
        exit(0);
    }
    for (int i=1; i<=va.m; i++){//将数据读入缓冲区，进行顺串构造
        fin1>>ssplayer[i].key;
        ssplayer[i].id=1;
        va.visitDiskTime++;//访存次数+1
    }
    MinimumLoserTree<SequentialStringPlayer> sstree(ssplayer,va.m);
    int num=0;
    for (int i=1; i<=va.n; i++){//依次从磁盘中取出元素，放入顺串生成树

        if(!(fin1>>num)) num=INT_MIN;
        else va.visitDiskTime++;

        SequentialStringPlayer tempwinner=ssplayer[sstree.getTheWinner()];
        SequentialStringPlayer tempnum; tempnum.key=num;

        if(num >= tempwinner.key) tempnum.id=tempwinner.id;
        else tempnum.id=num=(num==INT_MIN) ? INT_MAX :tempwinner.id+1;

        sstree.rePlay(sstree.getTheWinner(),tempnum);

        string smallfile=va.path+"smallfile"+to_string(tempwinner.id)+".txt";
        va.numberOfDisk=max(va.numberOfDisk,tempwinner.id);
        ofstream fout2(smallfile, ios::app);
        fout2<<tempwinner.key<<' ';

        fout2.close();
        va.visitDiskTime++;
    }
    fin1.close();
    cout<<"顺串分配完毕，生成"<<va.numberOfDisk<<"个顺串，顺串文件见您当前路径下出现的新文件"<<endl;
    if(va.ch1=='y'){
        cout<<"我们将这些数据在这里显示如下："<<endl;
        for (int i=1; i<=va.numberOfDisk; i++)
        {
            string smallfile=va.path+"smallfile"+to_string(i)+".txt";
            ifstream finx(smallfile);
            int tempx=0;
            cout<<"smallfile"<<i<<".txt: ";
            while(finx>>tempx)
                cout<<tempx<<' ';
            cout<<endl;
            finx.close();
        }
    }
}
void GenerateTheFinalResult(Variable &va)
{
    cout<<endl<<"请问是否将最终排序结果放入原文件，如果否，则程序将新建一个Disk2.txt文件并放入此文件中（输入'y'或'n'代表'是'与'否')："; cin>>va.ch;
    string newFile;
    if(va.ch=='y') newFile=va.file;
    else newFile=va.path+"Disk2.txt";

    ofstream fout3(newFile);

    if(va.numberOfDisk==1){//只生成了一个顺串文件，直接将其加入目标文件
        string smallfile=va.path+"smallfile"+to_string(1)+".txt";
        ifstream fin4(smallfile);
        int tempnumber;
        while(fin4>>tempnumber){
            fout3<<tempnumber<<' ';
            va.visitDiskTime+=2;
        }
        fout3.close();
        fin4.close();
        cout<<"由于只生成了1个顺串，直接将此结果放入目标文件中，磁盘访存次数为"<<va.visitDiskTime<<"次，原因是每个数据都读写4次"<<endl;
        if(va.ch1=='y'){
            cout<<"最终外排序结果如下："<<endl;
            ifstream finy(newFile);
            int tempy;
            while(finy>>tempy)
                cout<<tempy<<' ';
            cout<<endl;
            finy.close();
        }
        exit(0);
    }

    int dplayer[va.numberOfDisk+10];//初始化队列
    int pointer[va.numberOfDisk+10];//各个小磁盘文件的指针
    for (int i=1; i<=va.numberOfDisk; i++){
        string smallfile=va.path+"smallfile"+to_string(i)+".txt";
        ifstream fin2(smallfile);
        fin2>>dplayer[i];
        pointer[i]=fin2.tellg();
        fin2.close();
    }
    MinimumLoserTree<int> dtree(dplayer,va.numberOfDisk);
    int cnt=0;
    while(cnt<va.n){
        cnt++;
        int temp=dtree.getTheWinner();
        int tempwinner=dplayer[temp];
        fout3<<tempwinner<<' ';
        va.visitDiskTime++;
        string smallfile=va.path+"smallfile"+to_string(temp)+".txt";
        ifstream fin3(smallfile);
        fin3.clear(); fin3.seekg(pointer[temp]+1);

        int tempnum;
        if(pointer[temp]+1==0) tempnum=INT_MAX;
        else {
            fin3>>tempnum;
            pointer[temp]=fin3.tellg();
            if(pointer[temp]+1==0) tempnum=INT_MAX;
        }
        va.visitDiskTime++;
        dtree.rePlay(temp,tempnum);
        fin3.close();
    }
    fout3.close();
    cout<<endl;
    cout<<"将这些文件进行"<<va.numberOfDisk<<"路归并，已经结果存入到目标文件中。磁盘访存次数为"<<va.visitDiskTime<<"次，原因是每个数据都读写4次"<<endl;
    if(va.ch1=='y'){
        cout<<"最终外排序结果如下："<<endl;
        ifstream finy(newFile);
        int tempy;
        while(finy>>tempy)
            cout<<tempy<<' ';
        cout<<endl;
        finy.close();
    }
}
int main()
{
    srand(time(nullptr));
    Variable va;

    init(va);//初始化，生成随机磁盘文件

    SequentialStringPlayer ssplayer[va.n+10];

    SequentialStringConstruction(va,ssplayer);//构造顺串

    GenerateTheFinalResult(va);//生成最终结果

    return 0;
}

代码参考教材源码以及这篇博客

 赢者树总 ：

   C++(数据结构与算法):45---竞赛树/选择树（赢者树、输者树）_董哥的黑板报-CSDN博客    

//
//  main.cpp
//  winner
//
//  Created by 🐻先生 on 2021/11/21.
//

#include<iostream>
#include<queue>
using namespace std;
 
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;
};
struct player
{
    int id, key;
 
    operator int() const { return key; }
};
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);
    //返回最终赢者的索引
    int winner()const  { return this->tree[1]; }
    //返回竞赛树某个节点的赢者
    int winner(int i) const{
        return (i < this->numberOfPlayers) ? this->tree[i] : 0;
    }
    //在参赛者thePLayer的分数变化后重赛
    void rePlay(int thePlayer);
 
    //输出赢者树中的一些信息
    void output()const;
    void winnerToLoserTree();
    int RElowExt(){return lowExt;}         //供对象使用
    int REoffset(){return offset;}
    int* root(){return tree};
    int leftChild(int i){ if(i*2<numberOfPlayers-1) return temp*2; return 0;}
    int rightChild(int i){ if(i*2+1<numberOfPlayers-1) return temp*2+1; return 0;}
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;          //保存竞赛选手
};
template<class T>
void completeWinnerTree<T>::winnerToLoserTree(){
     queue<int>  q;//层次遍历  赢者树tree【i】 的孩子可以知道比赛的选手
     int temp;
     bool flag=1;
     int left,right,rightFirstPlayer;
     int s=numberOfPlayers-lowExt/2; //最后一个内部节点序号 反解
        q.push(1);
     while(!q.empty()){
         temp=q.front();
         q.pop();
         if(temp*2<numberOfPlayers-1){//反解定位到左子树
                left= player[ tree[temp*2] ];
                if(flag)
                  tree[0]= tree[temp*2];
         }
                  else if( temp*2>=s )
                    left= player[2*temp-offset];
                     else
                       left= player[2*temp+1+lowExt-numberOfPlayers];

         if(temp*2+1<numberOfPlayers-1){
               right=player[ tree[temp*2+1] ];
               if(flag)
                 rightFirstPlayer=tree[temp*2+1];
         }
               
                  else if( temp*2+1>=s )
                    right= player[2*temp-offset+1];
                     else
                       left= player[2*temp+1+lowExt-numberOfPlayers+1];
          if(flag){
              //赢者是最小的
              if(left>right)
                 tree[0]=rightFirstPlayer;
                   flag=0;
          }
            tree[temp]= left>right? left:right;
          if(temp*2<numberOfPlayers)
            q.push(temp*2);
           if(temp*2+1<numberOfPlayers)
             q.push(temp*2+1);
            
     }
      cout<<tree[0];
}
 
//用数组thePlayer[1:numberOfPlayers]生成赢者树
template<class T>
void completeWinnerTree<T>::initialize(T *thePlayer, int theNumberOfPlayers)
{
    int n = theNumberOfPlayers;//竞赛者的数量 //如果竞赛者的数目小于2，不能进行竞赛
    if (n < 2)
    {
           cout<<"error!"<<endl;
           exit(1);
    }
        
 
    //初始化类内数据成员
    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);//最底层外部节点个数（见公式） 13-1
    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)
{
    //因为为最小赢者树，所以返回值比较小的为赢者
    //* 将play 和replay 的<= 改为> 即为最大赢者树
    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)
         {
           cout<<"error!"<<endl;
           exit(1);
    }
 
    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])//0
        ? leftChild : rightChild;
 
    // 第二次比赛的特殊情况
    if (matchNode == n - 1 && n % 2 == 1)
    {
        matchNode /= 2;   // 移至父节点
        tree[matchNode] = (player[tree[n - 1]] > //0
            player[lowExt + 1]) ?
            tree[n - 1] : lowExt + 1;
    }
 
    // 玩剩下的比赛
    matchNode /= 2;  // 移至父节点
//*第 13.7题
    for (; matchNode >= 1; matchNode /= 2){
     int min  = (player[tree[2 * matchNode]] > //0
            player[tree[2 * matchNode + 1]]) ?
        tree[2 * matchNode] : tree[2 * matchNode + 1];

           if( tree[matchNode]  ==min)
              break;//只进行必要比较
               else
                  tree[matchNode]=min;
    }
        
}
struct binType{
     int unusedCapacity;
     int operator> (binType&x){
        return unusedCapacity> x.unusedCapacity;
     }
};
void
FFpack(int *objectSize,int numberOfObjects,int binCapacity){//FF 方案装载 利用最大赢者树
    int n=numberOfObjects;
    int usdBin=0,binToUse=0,ancestors=0;
    bool flag=0;
    binType *bin= new binType [n+1];
      for(int i=0;i<=n;i++){
            bin[i].unusedCapacity=binCapacity;
      }
    completeWinnerTree<binType> winner(bin,n);
    
      for(int i=1;i<=n;i++){
         //找公共祖先开始遍历
           if(usdBin==0)
              ancestors=(1+winner.REoffset())/2,usdBin++;
               else {
                   int firstFather=(1+winner.REoffset())/2;
                   int lastFather= usdBin<=winner.RElowExt()? (usdBin+winner.REoffset())/2:(usdBin-winner.RElowExt()+n-1)/2;
                 while(firstFather!=lastFather){
                       if(firstFather==1||lastFather==1)
                            break;
                     firstFather/=2;
                     lastFather/=2;
                    
                 }
                  ancestors=firstFather<lastFather? firstFather:lastFather;
               }
               //------
            while(ancestors<n){
                int winnerPlayer=winner.winner(ancestors);
                if(bin[winnerPlayer].unusedCapacity<objectSize[i]){
                    ancestors++;//此公共子树无空间
                    usdBin++;
                    binToUse=usdBin;
                    flag=1;
                    break;
                }
                ancestors*=2;
            }
            ancestors/=2;
     if(!flag)
         if(ancestors<n){
             binToUse=winner.winner(ancestors);
             if(binToUse>1&& bin[binToUse-1].unusedCapacity>=objectSize[i])//保证最左边
                binToUse--;
         }
          else
            binToUse= winner.winner(ancestors/2);
          else
            flag=0;
        cout<<"Pack object"<<i<<"in bin"<<binToUse<<endl;
        bin[binToUse].unusedCapacity-=objectSize[i];
        winner.rePlay(binToUse);
      
      }

}


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 <=n; i++)
    // {
    //     std::cin >> thePlayer[i].key;
    //     thePlayer[i].id = i;
    // }
    // completeWinnerTree<player> *w = new completeWinnerTree<player>(thePlayer, n);
 
    //  cout<<w->winner()<<endl;
 

  
    return 0;
}

   

  输者树总：

 外排序（最小输者树实现）_龙征天的博客-CSDN博客      

#include <iostream>
using namespace std;
template <class T>
class loserTree
{
public:
    virtual ~loserTree(){}
    virtual void initialize(T* thePlayer,int number)=0;
    virtual int getTheWinner() const =0;
    virtual void rePlay(int thePLayer,T newvalue)=0;
};
template <class T>
class MinimumLoserTree : public loserTree<T>
{
public:
    MinimumLoserTree(T* thePlayer=nullptr,int theNumberOfPlayers=0){
        tree=nullptr; advance=nullptr;
        initialize(thePlayer,theNumberOfPlayers);
    }
    ~MinimumLoserTree(){delete[] tree;delete[] advance;}
    void initialize(T* thePlayer,int theNumberOfPlayers);//初始化
    int getTheWinner() const {return tree[0];};//输出当前的赢者
    void rePlay(int thePlayer,T newvalue);//重构
private:
    int numberOfPlayers;
    int* tree;//记录内部结点，tree[0]是最终的赢者下标，不使用二叉树结点，因为父子关系都是通过计算得出
    int* advance;//记录比赛晋级的成员
    T* player;//参与比赛的元素
    int lowExt;//最底层外部结点的个数,2*(n-s)
    int offset;//2*s-1
    void play(int,int,int);
    int winner(int x,int y){return player[x]<=player[y]?x:y;};//返回更小的元素下标
    int loser(int x,int y){return player[x]<=player[y]?y:x;};//返回更大的元素下标
};
template <class T>
void MinimumLoserTree<T>::initialize(T* thePlayer,int theNumberOfPlayers)
{
    int n=theNumberOfPlayers;
    if(n<2) {
        cout<<"Error! the number must >= 2"<<endl;
        return;
    }
    player=thePlayer;
    numberOfPlayers=n;
    delete[] tree; delete[] advance;
    tree=new int[n+1];
    advance=new int[n+1];

    int s; for (s=1; 2*s<=n-1; s+=s);//s=2^log(n-1)-1（常数优化速度更快），s是最底层最左端的内部结点

    lowExt=2*(n-s); offset=2*s-1;

    for (int i=2; i<=lowExt; i+=2)//最下面一层开始比赛
        play((i+offset)/2,i-1,i);//父结点计算公式第一条

    int temp=0;
    if(n%2==1){//如果有奇数个结点，处理下面晋级的一个和这个单独的结点
        play(n/2,advance[n-1],lowExt+1);
        temp=lowExt+3;
    }
    else temp=lowExt+2;//偶数个结点，直接处理次下层

    for (int i=temp; i<=n; i+=2)//经过这个循环，所有的外部结点都处理完毕
        play((i-lowExt+n-1)/2,i-1,i);

    tree[0]=advance[1];//tree[0]是最终的赢者，也就是决赛的晋级者
    cout<<tree[0]<<endl;

}
template <class T>
void MinimumLoserTree<T>::play(int p, int leftChild, int rightChild)
{
    //tree结点存储相对较大的值，也就是这场比赛的输者
    tree[p]=loser(leftChild,rightChild);
    //advance结点存储相对较小的值，也就是这场比赛的晋级者
    advance[p]=winner(leftChild,rightChild);

    while(p % 2 == 1 && p > 1){
        tree[p/2]=loser(advance[p-1],advance[p]);
        advance[p/2]=winner(advance[p-1],advance[p]);
        p /= 2;//向上搜索
    }
}
template <class T>
void MinimumLoserTree<T>::rePlay(int thePlayer,T newvalue)
{
    int n=numberOfPlayers;
    if(thePlayer <= 0 || thePlayer > n){
        cout<<"Error! the number must >0 & <=n"<<endl;
        return;
    }

    player[thePlayer]=newvalue;

    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=advance[2*matchNode];
            rightChild=thePlayer;
        }
        else{
            leftChild=2*matchNode-n+1+lowExt;//这个操作是因为上面matchNode计算中/2取整了
            rightChild=leftChild+1;
        }
    }
    //到目前位置，我们已经确定了要比赛的场次以及比赛的选手

    //下面进行比赛重构，也就是和赢者树最大的不同，分两种情况
    if(thePlayer==tree[0]){//当你要重构的点是上一场比赛的赢家的话，过程比赢者树要简化
        for (; matchNode>=1; matchNode/=2){
            int oldLoserNode=tree[matchNode];//上一场比赛的输者
            tree[matchNode]=loser(oldLoserNode,thePlayer);
            advance[matchNode]=winner(oldLoserNode,thePlayer);
            thePlayer=advance[matchNode];
        }
    }
    else {//其他情况重构和赢者树相同
        tree[matchNode]=loser(leftChild,rightChild);
        advance[matchNode]=winner(leftChild,rightChild);
        if(matchNode==n-1 && n%2==1){//特殊情况，比赛结点是最后一层的最后一场比赛
            //特殊在matchNode/2后，左儿子是晋级的选手，右儿子是一场都没有比过赛的选手
            matchNode/=2;
            tree[matchNode]=loser(advance[n-1],lowExt+1);
            advance[matchNode]=winner(advance[n-1],lowExt+1);
        }
        matchNode/=2;
        for (; matchNode>=1; matchNode/=2){
            tree[matchNode]=loser(advance[matchNode*2],advance[matchNode*2+1]);
            advance[matchNode]=winner(advance[matchNode*2],advance[matchNode*2+1]);
        }
    }
    tree[0]=advance[1];//最终胜者
}

int main()
{
    int player[]={0,9,6,8,4,5};
  MinimumLoserTree<int> a(player,5);
  
  


    return 0;
}

13.1-4

   

     重构只需要从此位置遍历到根         

13.5

    小根堆： 

       p个元素的小根堆

      输出top  然后改变root 的值 ，相当于换值

      时间复杂度   log（p） ，输出的方法跟书上一样

  优点：赢者树知道每一个比较的结果 缺点： 需要n-1个内部节点 

13.6

    思路跟赢者树一致

也是p个元素的小根堆分别代表p个归并段的头元素 

  由于初始化都是O（n）  输出都是log（n） 

  优缺点应该与上题一致

13.7

      修改部分判断

//*第 13.7题
    for (; matchNode >= 1; matchNode /= 2){
     int min  = (player[tree[2 * matchNode]] <=
			player[tree[2 * matchNode + 1]]) ?
		tree[2 * matchNode] : tree[2 * matchNode + 1];

           if( tree[matchNode]  ==min) 
              break;//只进行必要比较
               else 
                  tree[matchNode]=min;  
    }

   

13.8

    

template<class T>
void winnerSort(T* element,int size);
 template<class T>
void winnerSort(T* element,int size){
      
	  thePlayer = new player[size+1];
       T temp;
	for (int i = 1; i <=size; i++)
	{
		 thePlayer[i].key=element[i];
         thePlayer[i].id=i;
	}
    completeWinnerTree<player> *w= new completeWinnerTree<player>(thePlayer, size);
    for (int i = 1; i <=size; i++){
        temp=w->winnerElement();
		cout<<temp<<endl;
         element[i]=temp;
        thePlayer[w->winner()].key = 65535;//至一个最大不可能值
          w->rePlay(w->winner()) ;
    }
       
}

13.9

   不会更简单

13.10

    不用其他判断，全在最底层了 

     

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

   只需要这个即可 

13.11

   1）

      

2）

       player【n+1:m】 没有定义的地方直接直接无穷大，然后比较 

     其他操作一致

   差别不大，同10简化了父节点过程 

13.12

    感觉相差不大，都是把非一般情况去除 ，而且还多比了几次？

13.13

   跟11题一样 

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

  这一情况不用考虑 ，未定义的player为∞ 

  

   都是 用空间 简化代码，但是并没有提高效率，甚至还要多比较几次

13.14

 赢/输   replayer区别：

        当改变的是赢者时：  这条路径都要重新比较

                         输者树：不用查看比较的另一孩子（兄弟），因为必然存在内节点（比赛节点）中

                         赢者树：要查看内部节点的另一孩子（兄弟），以比较

       当改变的是任意玩家时： 不一定要比较此条路径，若与父节点结果一致，则无需比较祖父节点。。

                         输者树和赢者输一样：都要查看另一孩子以比较

     

   

1) 看总 

2）   赢者树转输者输

        

template<class T>
void completeWinnerTree<T>::winnerToLoserTree(){
     queue<int>  q;//层次遍历  赢者树tree【i】 的孩子可以知道比赛的选手
     int temp;
     bool flag=1;
     int left,right,rightFirstPlayer;
     int s=numberOfPlayers-lowExt/2; //最后一个内部节点序号 反解
        q.push(1);
     while(!q.empty()){
         temp=q.front();
         q.pop();
         if(temp*2<numberOfPlayers-1){//反解定位到左子树
                left= player[ tree[temp*2] ];
                if(flag)
                  tree[0]= tree[temp*2];
         }
                  else if( temp*2>=s )
                    left= player[2*temp-offset];
                     else 
                       left= player[2*temp+1+lowExt-numberOfPlayers];  

         if(temp*2+1<numberOfPlayers-1){
               right=player[ tree[temp*2+1] ];
               if(flag)
                 rightFirstPlayer=tree[temp*2+1];
         }
               
                  else if( temp*2+1>=s )
                    right= player[2*temp-offset+1];
                     else 
                       left= player[2*temp+1+lowExt-numberOfPlayers+1];  
          if(flag){
              //赢者是最小的
              if(left>right)
                 tree[0]=rightFirstPlayer;
                   flag=0;
          }
            tree[temp]= left>right? left:right;
          if(temp*2<numberOfPlayers)
            q.push(temp*2);
           if(temp*2+1<numberOfPlayers)
             q.push(temp*2+1);
            
     }   
      cout<<tree[0];  
}

    3）

       从下往上递归？ 

    

    4）

        相当于中断的中序遍历

从未比赛的最左节点向上遍历 当不知道另一个选手时，停止 并用此比赛节点暂时记录唯一选手。 重复此过程

 13.20 

        一样的，去掉很多情况

13.21:

     不想写，累死了 ，思路如书上所说

13.22

    O（nlogn） 

       结果不对，哪错了呢

template<class T>
void
loserTreeSort(T* array,int Size){
       MinimumLoserTree<int> loserTree(array,Size);
        for(int i=1;i<=Size;i++){
            array[i]= loserTree.winnerValue();
             loserTree.rePlay(loserTree.getTheWinner(),65535);
        }
}

   

13.23

 1）

      最优：1，3装一号箱子 2，4，5 装二号箱子 ，一共两个箱子 

2）

四种近似装载方法：

    FF：装入能装的最左箱子  

              1，2 /3，4/5  一共三个箱子

    BF：装入最接近物品大小的箱子 >= bojectSize[i] 

              同FF 一共三个箱子 

    FFD：先递减排序 然后FF

             需要两个箱子

     BFD：先递减排序 然后BF

            需要两个箱子

  3） 

     FF和BF 3/2 

     FFD和BFD 1/1

13.24

   自己写 按原则

13.25

     关键是找到公共节点 和此子树不行时 直接启用新箱子，剩下思路与书上列一致

写的很乱。。

void
FFpack(int *objectSize,int numberOfObjects,int binCapacity){//FF 方案装载 利用最大赢者树
    int n=numberOfObjects;
    int usdBin=0,binToUse=0,ancestors=0;
    bool flag=0;
    binType *bin= new binType [n+1];
      for(int i=0;i<=n;i++){
            bin[i].unusedCapacity=binCapacity;
      }
    completeWinnerTree<binType> winner(bin,n);
    
      for(int i=1;i<=n;i++){
         //找公共祖先开始遍历
           if(usdBin==0)
              ancestors=(1+winner.REoffset())/2,usdBin++;
               else {
                   int firstFather=(1+winner.REoffset())/2;
                   int lastFather= usdBin<=winner.RElowExt()? (usdBin+winner.REoffset())/2:(usdBin-winner.RElowExt()+n-1)/2;
                 while(firstFather!=lastFather){
                       if(firstFather==1||lastFather==1)
                            break;
                     firstFather/=2;
                     lastFather/=2;
                    
                 }
                  ancestors=firstFather<lastFather? firstFather:lastFather;
               }
               //------
            while(ancestors<n){
                int winnerPlayer=winner.winner(ancestors);
                if(bin[winnerPlayer].unusedCapacity<objectSize[i]){
                    ancestors++;//此公共子树无空间
                    usdBin++;
                    binToUse=usdBin;
                   flag=1;
                    break;
                }
                ancestors*=2;
            }
            ancestors/=2;
     if(!flag)
         if(ancestors<n){
             binToUse=winner.winner(ancestors);
             if(binToUse>1&& bin[binToUse-1].unusedCapacity>=objectSize[i])//保证最左边
                binToUse--;
         }
          else
            binToUse= winner.winner(ancestors/2);
          else
            flag=0;
        cout<<"Pack object"<<i<<"in bin"<<binToUse<<endl;
        bin[binToUse].unusedCapacity-=objectSize[i];
        winner.rePlay(binToUse);
      
      }

}

   

13.26

    返回的是孩子的比赛结果还是地址？还是下标

 int* root(){return tree};
    int leftChild(int i){ if(i*2<numberOfPlayers-1) return temp*2; return 0;}
    int rightChild(int i){ if(i*2+1<numberOfPlayers-1) return temp*2+1; return 0;}

13.27

   假设n件物品最优总占用空间为x =n*size

   最差情况下每个箱子刚好不能装下此物品-- > 每一箱子浪费趋近于size空间   -->最多浪费趋近于

size*n空间 <=x

   所以不可能大于比例不可能大于2 

13.28

    自行实验，估计是FFD效率最高

13.29

     利用root，left，right函数方法 照书上实现

      书上的程序返回的是适用的箱子 

13.30 

  从启用箱子右端开始搜索 ，与FF方向相反 

   时间也是O（nlogN）

 

      

     

                                                   十三章总结

本章主要讲了 决策树（输/赢）「

 都是用模拟指针（数组）的方式来实现 

  用一个player数组来代表选手

  数本身内节点用来记录胜负(记录选手的下标，player【下标】就是选手的值】

」

  a 输赢 区别：参看13.14

  b 与大根堆的区别： 大部分操作的复杂度都相同O（nlogn）初始化O（n） 

            但一些间断性的操作时，就要选择决策树

 应用： 

    1.装载箱子问题 ：

          模拟算法有四种 ：查看13.23 

          相邻适配：循环搜索，先从上次使用的箱子 右边开始 到 未启用箱子为止，若未找到，则从

左边搜索直至完成一次循环，最坏情况下就是循环一圈启用新箱子

     2.还可以用决策树来排序，通过replay方法来隐式的排除取到的值 

 还需努力，加油！！！！

         

      

  

            

• 本文代码下载：
  • 方式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)，采用输者树比采用赢者树执行效率更高