C++胜者树

#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, i, 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,0,22,-1,33,5};
    Grial(a, 11);
    return 0;
}

胜者树类似于冒泡排序的优化，记录已经比较的，去掉不必比较的，
将最小的不停冒泡选出，最终得到结果，跟堆十分类似。

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点！
本站所提供的图片等素材，版权归原作者所有，如需使用，请与原作者联系。