精华内容
下载资源
问答
  • 最小输者树
    2021-03-22 13:19:38

    赢者树(WinnerTree)输者树(LoserTrees).ppt

    Chapter10 Tournament Trees 赢者树(Winner Tree) 输者树(Loser Trees) 竞赛树 赢者树 定义[赢者树] 对于n 名选手,赢者树是一棵含n 个外部节点,n-1个内部节点的完全二叉树,其中每个内部节点记录了相应赛局的赢家。 赢者树 赢者树优点 即使一名选手得分改变了,也可以较容易地修改此树。。 例 如当选手d的值由9改为1时,只需沿从d 到根那条路径修改二叉树,而不必改变其他比赛的结果。 有时甚至还可以避免重赛某些场次。如当b 值由6改为5时,其父节点的比赛结果中b仍为输家,故此时所有比赛的结果未变,因此不必重赛b 的祖父及曾祖父节点所对应的比赛。 赢者树分析 对于一棵有n 名选手的赢者树,当一个选手的得分发生变化时,需要修改的比赛场次介于0~log2n 之间,因此重构赢者树需耗时O(logn)。 由于n 名选手的赢者树在内部节点中共需进行n - 1场比赛(按从最低层到根的次序进行),因此赢者树的初始化时间为Θ(n)。 赢者树应用-排序 可用一个最小赢者树在Θ(nlogn)时间内对n个元素进行排序。 赢者树应用-排序 首先,用n个元素代表n名选手对赢者树进行初始化。利用元素的值来决定每场比赛的结果,最后的赢家为具有最小值的元素,然后将该选手(元素)的值改为最大值(如∞),使它赢不了其他任何选手。 在此基础上,重构该赢者树,所得到的最终赢家为该排序序列中的下一个元素。 以此类推,可以完成n个元素的排序。 赢者树应用-排序 初始化赢者树的时耗为Θ(n)。 每次改变竞赛赢家的值并重构赢者树的时耗为Θ(logn),这个过程共需执行n-1次。 因此整个排序过程所需要的时间为Θ(nlogn)。 外部排序 外部排序法(external sorting method)一般包括两步: 产生部分排序结果run; 将这些run合并在一起得到最终的run。 外部排序例 假设要为含16000个元素的记录排序,且在内部排序中一次可排序1000个记录。 外部排序例 在第1)步中,重复以下步骤16次,可得到16个排序结果(run): 输入1000个记录 用内部排序法对这1000个记录进行排序 输出排序结果run 外部排序例 2.在第2)步中,重复地将k个run合并成 一个run。 合并k个run的简单方法 从k个run的前面不断地移出值最小的元素,该元素被移至输出run中。当所有的元素从k个输入run移至输出run中时,便完成了合并过程。 只要有足够内存保存k个元素值,就可合并任意长度的k个run。 在实际应用上,感兴趣的是能一次输入/出更多元素以减少输入/出的次数。 外部排序例续 在上面所列举的16000个记录的例子中,每个run有1000个记录,而内存容量亦为1000个记录。 为合并前四个run,可将内存分为五个缓冲区,每个容量为200个记录。其中前四个为输入run的缓冲区,第五个为输出run的缓冲区,用于存放合并的记录。 外部排序例续 从四个输入run中各取200个记录放入输入缓冲区中,这些记录被不断地合并并放入输出缓冲区中,直到以下条件发生: 输出缓冲区已满。 某一输入缓冲区空。 外部排序例续 当输出缓冲区已满时,将输出缓冲区内容写入磁盘,写完之后继续进行合并。 当某一输入缓冲区空时,则从对应于空缓冲区的输入run中继续读取记录放入该缓冲区,读取过程结束后合并继续进行。 当这些run中的4000个记录都写入输出run中时,四个run的合并过程结束 k路合并 k个run要合并成一个排好序的run。 因在每一次循环中都需要找到最小值,故将每一个元素合并到输出run中需O(k)时间,因此产生大小为n的run所需要的时间为O(kn)。 若使用赢者树,则可将这个时间缩短为Θ(k+nlogk)。 k路合并 首先用(k)的时间初始化含k个选手的赢者树。这k个选手都是k个被合并run中的头一个元素。 然后将赢者移入输出run中并用相应的输入run中的下一个元素替代之。如果在该输入run中无下一元素,则需用一个key值很大(不妨为∞)的元素替代之。 k次移入和替代赢家共需耗时Θ(logk)。因此采用赢者树进行k路合并的总时间为Θ(k+nlogk)。 * * *

    更多相关内容
  • 外排序(最小输者树实现)

    千次阅读 多人点赞 2020-04-07 11:30:24
    (1) 设计实现最小输者树结构ADT,ADT中应包括初始化、返回赢者,重构等基本操作。 (2) 设计实现外排序,外部排序中的生成最初归并串以及K路归并都应用最小输者树结构实现; (3) 随机创建一个较长的文件;设计...

    问题描述

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

    基本要求

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

    解题

    输者树介绍

    对于输者树的构建过程,数据结构课本上并没有多说,仅仅讲解了赢者树,如下图所示,赢者上升进入下一次比赛。
    最小赢者树
    哦,原来这就是赢者树,那么这个最小赢者树是不是就是最大输者树了呢?

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

    后来在网上看了一些博客才懂什么意思,我们下面看一下课本上这个图是怎么建立起来的:
    在这里插入图片描述
    这棵树上,边的值才是比赛晋级的选手,而不是赢者树中结点的才是晋级。

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

    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;
    }
    

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

    展开全文
  • 13.1-4 重构只需要从此位置遍历到根 ... 优点:赢者知道每一个比较的结果 缺点: 需要n-1个内部节点 13.6 思路跟赢者一致 也是p个元素的小根堆分别代表p个归并段的头元素 由于初始化都是O(n...

     赢者树总 :

       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方法来隐式的排除取到的值 

     还需努力,加油!!!!

             

          

      

                

    展开全文
  • 竞赛的基本操作是替换最大(或最小)元素。如果有n个元素,这个基本操作的用时为Θ(logn)。虽然也能用堆和左高树来表示也能用近似的时间(O(logn))完成这个操作,但是用来实现可预见的断接操作都不容易 当我们...

    一、竞赛树概述

    • 竞赛树是完全二叉树(或满二叉树)
    • 竞赛树可以用数组来表示,而且存储效率最高
    • 竞赛树的基本操作是替换最大(或最小)元素。如果有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(\logn\log n)

    赢者树的排序

    • 步骤:
      • 我们假设对最小赢者树进行排序(那么最终的赢者就是关键字值最小的元素)
      • 我们在所有的元素中选出关键字最小的元素,将该元素的关键字值改为最大值(假设为),使它赢不了剩余的其它任何选手
      • 然后重构赢者树,这时的总冠军是排序在第二的元素。同样的道理,将该元素的关键字也改为最大值(假设为),使它也赢不了剩余的其它任何选手
      • 依次类推,再一次重构赢者树......最终就可以完成n个元素的排序
    • 复杂度:
      • 赢者树初始化的用时为Θ(n)。每次改变赢者的关键字并重构赢者树的用时为Θ(\log n),因为在从一个外部节点到根的路径上,所有的比赛需要重赛。赢者树的重构共需n-1次。因此,整个排序过程的时间为Θ(n+n\log n)=Θ(n\log 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),采用输者树比采用赢者树执行效率更高
    展开全文
  • [摘要] 选择一颗生成,使之总的消费最少,也就是要构造连通网的最小代价生成(简称为最小生成)的问题,一颗生成的代价就是上各边的代价之和,构造最小生成树可以有多种算法,其中多数算法利用了MST的性质...
  • 最小方差生成

    2018-05-18 15:17:58
    最小方差生成 问题描述给定带权无向图,求出一颗方差最小的生成。输入格式输入多组测试数据。第一行为N,M,依次是点数和边数。接下来M行,每行三个整数U,V,W,代表连接U,V的边,和权值W。保证图连通。n=m=0标志...
  • 最小生成的Kruskal算法 一、 什么是最小生成 1.1 最小生成定义: 一个有 n 个结点的连通图的生成是原图的极小连通子图,且包含原图中的所有 n 个结点,并且有保持图连通的最少的边。最小生成可以用...
  • 而一幅图的生成有很多种,其中最小生成指的是带权图的生成中边权和最小。并且若图中的边权都不相同,则最小生成唯一(每两个节点都只有一条边相连,每次选最小的),反之,就不一定了。 最小生成树一般...
  • N个点M条边的无向连通图,每条边有一个权值,求该图的最小生成。 Input 第1行:2个数N,M中间用空格分隔,N为点的数量,M为边的数量。(2 &lt;= N &lt;= 1000, 1 &lt;= M &lt;= 50000)  第2 - M...
  • SDUT 最小生成

    2018-05-28 21:05:57
    最小生成Time Limit: 1000 ms Memory Limit: 65536 KiBSubmit StatisticProblem Description在一个无向图中,求最小生成。Input多组测试数据,对于每组测试数据,第1行输入正整数n(1 &lt;= n &lt;= ...
  • 最小生成 Time Limit:1000 msMemory Limit:65536 KiB SubmitStatistic Problem Description 在一个无向图中,求最小生成。 Input 多组测试数据,对于每组测试数据,第1行输入正整数n(1 <= n <= 1000...
  • 设计程序完成如下功能:对于任意给定的的网和起点,用PRIM算法的基本思想求解出所有的最小生成
  • 给定一个带权无向图,如果是连通图,则至少存在一棵最小生成,有时最小生成树并不唯一。本题就要求你计算最小生成的总权重,并且判断其是否唯一。 输入格式: 首先第一行给出两个整数:无向图中顶点数N(≤500...
  • #include #include #include #define INFINITY INT_MAX #define MAX_VERTEX_NUM 20 //最大顶点数为20// typedef int VRType; typedef int InfoType; typedef char VerTexType;...typedef struct ArcCell // 邻接...
  • 算法介绍 贪心算法: 贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。即通过每次贪最优的情况,直到问题结束,是通过局部最优...①将所有顶点放入集合V{}中,设最小生成顶点集S{}
  • 在游戏上使用最小-最大算法实现。 该应用程序可在浏览器中运行。 您可以在线尝试 安装 克隆存储库。 git clone https://github.com/adijo/min-max-tic-tac-toe.git 输入目录。 cd min-max-tic-tac-toe 。 安装...
  • 图论——最小生成之Prim算法 普里姆算法(Prim算法),图论中的一种算法,可在加权连通图里搜索最小生成。意即由此算法搜索到的边子集所构成的中,不但包括了连通图里的所有顶点(英语:Vertex (graph theory...
  • kruskal从一个上帝视角将所有的边的权值从小到大排列出来,然后再从小到大选择路径就好,这 样可以很好的构建图的最小生成,需要注意的是需要写一个Find函数来判断是否会形成回路,导 致构建的并非最小生成 3....
  • Prim算法求最小生成

    2019-12-02 20:18:35
    设G=(V,E)是无向连通网,T=(U,TE)是G的最小生成,Prim算法的基本思想是:从初始状态U={v}(v∈V)、TE={ }开始,重复执行下述操作:在所有i∈U,j∈V-U的边中找一条代价小的边(i,j)并人集合TE,同时j...
  • 采用Prim算法构造最小生成 2.解析 Prim算法基本思想:   假设G=(V,E)是连通的,TE是G上最小生成中边的集合。算法从U={u0}(u0∈V)、TE={}开始。重复执行下列操作:在所有u∈U,v∈V-U的边(u,v)∈E中找...
  • Prim算法生成最小生成详解

    千次阅读 2018-03-08 22:31:52
    创建一个low数组代表相应每个节点连接所需最小费用,一个vis数组标记相应节点是否连接过。low数组的初始值用节点1到其余各点的费用来填充如该图所示low数组的初始值应该为:06345以上便是1号节点对于其他各点的费用...
  • 最小生成的实现

    2011-12-05 17:14:22
    通过利用kruskal原理编程实现生成最小生成的代码
  • Prim算法求最小生成,Dijkstra算法求最短路径。 两者原理和代码结构基本相同,一石二鸟啦。
  • 连通图最小生成的算法及实现

    千次阅读 2016-11-30 15:30:00
    上面2个图都是第一个完全图的生成,但是2是完全不同的。 按照深度优先遍历生成的生成,称为深度优先生成 按照广度优先遍历生成的生成,称为广度优先生成   非连通图的生成森林,概念比较...
  • 洛谷-P3366 最小生成

    2018-10-09 16:10:35
    如题,给出一个无向图,求出最小生成,如果该图不连通,则输出orz 输入输出格式 输入格式: 第一行包含两个整数N、M,表示该图共有N个结点和M条无向边。(N&lt;=5000,M&lt;=200000) 接下来M行每行包含三...
  • 最小生成讲解

    千次阅读 2016-08-18 16:00:23
    最小生成 克鲁斯卡尔算法 普里姆算法
  • 几分钟搞明白生成最小生成的定义

    万次阅读 多人点赞 2017-11-15 07:57:53
    注意文字意思:不管是生成还是最小生成一定还是,千万别和图混淆了。下面来说生成:我们这棵是针对图来说的,如果你们已经知道极小连通子图就非常简单了, 极小连通子图什么意思呢,就是我们把图中的全部...
  • //最小生成最小生成的边集存于数组CT中 { int i,j,k,min,t,m,w; //给CT赋初值,对应第0次的LW值 for(i = 0; i ; i++) { CT[i].fromvex = 0; CT[i].endvex = i+1; CT[i].weight = GA[0][i+1]; } ...
  • 1.用邻接矩阵表示无向图更方便,之后在遍历和生成最小生成时需要不断访问 2.好好理解Prim算法中的lowcost[ ]数组和adjver[ ]数组,虽然adjver[ ] 数组在Prim算法中没什么用 3.Prim的主要思想映射到lowcost[ ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 12,633
精华内容 5,053
关键字:

最小输者树