加入收藏 | 设为首页 | 会员中心 | 我要投稿 李大同 (https://www.lidatong.com.cn/)- 科技、建站、经验、云计算、5G、大数据,站长网!
当前位置: 首页 > 百科 > 正文

C++胜者树

发布时间:2020-12-16 07:43:44 所属栏目:百科 来源:网络整理
导读:今天PHP站长网 52php.cn把收集自互联网的代码分享给大家,仅供参考。 #include iostream#define MAX_VALUE 0x7fffffffusing namespace std;//在这里我先反思一下,不知道怎么搞的,这个算法耗费我3个小时,惨不忍睹。void

以下代码由PHP站长网 52php.cn收集自互联网

现在PHP站长网小编把它分享给大家,仅供参考

#include <iostream>
#define MAX_VALUE 0x7fffffff
using namespace std;
//在这里我先反思一下,不知道怎么搞的,这个算法耗费我3个小时,惨不忍睹。
void DealWhat(int b[],int n,int flags)//每一次在n位置调整该位置的与子树的大小关系。
{
    int left = 2 * n + 1;
    int right = 2 * n + 2;
    if (left > flags)//左右子树都不是内部节点。
    {
        if (b[left] > b[right])
            b[n] = right;
        else b[n] = left;
    }
    else if (left == flags && right > flags)//左子树是内部节点,右子树不是。
    {
        if (b[b[left]] > b[right])
            b[n] = right;
        else
            b[n] = b[left];
    }
    else//是完全内部结点。
    {
        if (b[b[left]] > b[b[right]])
            b[n] = b[right];
        else b[n] = b[left];
    }
}
void Grial(int a[],int n)
{
    int size = 2 * n - 1;
    int *b = new int[size];
    int k = size-1;
    int i = n - 1;
    while (i>=0)
    {
        b[k--] = a[i];
        i--;
    }
    i = size / 2-1;
    int flags = i;//标记值,用来判断节点是不是完全内部节点,就是该节点的子节点不是叶子节点。
    while (i>=0)
    {
        DealWhat(b,i,flags);//初始化构造胜者树。
        i--;
    }
    int *save = new int[n];//vs2013下面不能修改a[i]的值,我试着将a数组直接保存求得
    k = 0;                 //的数字,可是总是报错,惆怅了半天。          
    i = 1;
    while (k < n)
    {
        save[k++] = b[b[0]];
        b[b[0]] = MAX_VALUE;//每次取走该位置的这个值后,将该位置的值设为无穷大。
        i = (b[0] -1) /2 ;
        while (i >= 0)
        {   

            DealWhat(b,flags);
            if (i == 0)break;
            i = (i - 1)/2;//此处每次操作完毕之后朝父亲节点移动。
        }
    }
    for (i = 0; i < n; i++)
    {
        cout << save[i] << "  ";
    }
    cout << endl;
    delete[]b;
    b = nullptr;//vs2013里面的NULL=nullptr。
}
int main()
{
    int a[] = {2,3,4,1,7,6,22,-1,33,5};
    Grial(a,11);
    return 0;
}
胜者树类似于冒泡排序的优化,记录已经比较的,去掉不必比较的,
将最小的不停冒泡选出,最终得到结果,跟堆十分类似。

以上内容由PHP站长网【52php.cn】收集整理供大家参考研究

如果以上内容对您有帮助,欢迎收藏、点赞、推荐、分享。

(编辑:李大同)

【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容!

    推荐文章
      热点阅读