#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;
}胜者树相似于冒泡排序的优化，记录已经比較的，去掉不必比較的，
将最小的不停冒泡选出。终于得到结果。跟堆十分相似。