胜者树与败者树是完全二叉树。就像是参加比赛一样，每个选手有不同的实力，两个选手
问题：有20个有序数组，每个数组有500个uint变量，降序排序。要求从这10000个元素中选出最大的500个。
程序：
#include <iostream>#include <vector>#include <cmath>#include <ctime>#include <algorithm>/****Author: w397090770*Data : 2012.10.15*Email : wyphao.2007@163.com*转载请注明出处，谢谢。 **/ #define N 10#define INF (1 << 31) – 1using namespace std;typedef struct Node{int which;//记录是哪个子数组 int index;//记录是上个标记数组的第几个元素了 int data;//记录数组的元素 }Node;int com(const void *a, const void *b){if(*(int *)a > *(int *)b){return 1;}else if(*(int *)a < *(int *)b){return -1;}return 0;}void adjustTreeForFirst(Node *tempArray, int len){int i = len / 2;int j = 0;while(i > 1){for(j = i; j < 2 * i – 1; j += 2){if(tempArray[j].data > tempArray[j + 1].data){tempArray[j / 2] = tempArray[j + 1];}else{tempArray[j / 2] = tempArray[j];}}i /= 2;}}//col 是列//row 是行//len 是选择出前多少个元素 void winTree(int **a, int row, int col, int len){int *result = (int *)malloc(len * sizeof(int));Node tempArray[row * 2];int index = 0;int i = 0, j = 0;memset(tempArray, 0, sizeof(struct Node) * 2 * row);for(i = 0; i < row; i++){tempArray[row + i].data = a[i][0];tempArray[row + i].which = i;tempArray[row + i].index = 0;}for(i = 0 ; i < len; i++){adjustTreeForFirst(tempArray, 2 * row);//为了代码减少代码量，我把每一次调用都调整整个树，，其实是不必要的，有兴趣的用户可以自己写写result[i] = tempArray[1].data;if(tempArray[1].index + 1 < col){tempArray[row + tempArray[1].which].data = a[tempArray[1].which][tempArray[1].index + 1];tempArray[row + tempArray[1].which].index = tempArray[1].index + 1;tempArray[row + tempArray[1].which].which = tempArray[1].which;}else{//如果某个数组里面的数据处理完了，就把那个节点赋值为无穷大tempArray[row + tempArray[1].which].data = INF;//tempArray[row + tempArray[1].which].index = tempArray[1].index + 1;//tempArray[row + tempArray[1].which].which = tempArray[1].which;}}for(i = 0; i < len; i++){cout << result[i] << endl;}free(result);}int main(){/*int a[N – 2][N] = {3, 4, 5, 6, 10, 11, 12, 13, 20, 21, 1, 2, 7, 8, 9, 30, 31, 32, 33, 34,14, 15, 16, 17, 18, 19, 22, 23, 24, 25,26, 27, 28, 29, 35, 36, 37, 38, 39, 40,50, 51, 52, 54, 55, 65, 66, 67, 68, 69,53, 56, 57, 58, 59, 60, 61, 62, 63, 64,41, 42, 43, 44, 45, 46, 47, 48, 49, 2222,1, 2, 2, 4, 5, 6, 12, 13, 20, 21};*/const int size = 500;const int del = 20;int *a[del];int i = 0, j = 0;//分配内存空间 for(i = 0; i < del; i++){ a[i] = (int *)malloc(size * sizeof(int)); }//初始化数组 srand( time(NULL) ); for(i = 0; i < size; i++){for(j = 0; j < del; j++){a[j][i] = rand();}}//排序 for(i = 0; i < del; i++){qsort(a[i], size, sizeof(int), com);}//利用胜利树进行处理 winTree(a, del, size, size);return 0;}二、败者树
败者树是胜者树的一种变体。在败者树中，用父结点记录其左右子结点进行比赛的败者，而让胜者参加下一轮的比赛。败者树的根结点记录的是败者，需要加一个结点来记录整个比赛的胜利者。采用败者树可以简化重构的过程。
转载请注明：
你会发现，曾经以为很难做到的事情，
