数据结构：胜者树与败者树

图一

图二

问题：有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) - 1 
using 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;
}