假設(shè)有k個稱為順串的有序序列，我們希望將他們歸并到一個單獨(dú)的有序序列中。每一個順串包含一些記錄，并且這些記錄按照鍵值的大小，以非遞減的順序排列。令n為k個順串中的所有記錄的總數(shù)。并歸的任務(wù)可以通過反復(fù)輸出k個順串中鍵值最小的記錄來完成。鍵值最小的記錄的選擇有k種可能，它可能是任意有一個順串中的第1個記錄。并歸k個順串的最直接的辦法就是進(jìn)行k-1次比較確定下一個輸出的記錄。對k>2，我們可以通過使用選擇數(shù)這種數(shù)據(jù)結(jié)構(gòu)來降低尋找下一個最小元素所需要進(jìn)行的比較次數(shù)。有兩個種選擇樹：勝利樹和失敗樹。
勝者樹與敗者樹是完全二叉樹。就像是參加比賽一樣，每個選手有不同的實(shí)力，兩個選手PK,實(shí)力決定勝負(fù)，晉級下一輪，經(jīng)過幾輪之后，就能得到冠軍。不同的是，勝者樹的中間結(jié)點(diǎn)記錄的是勝者的標(biāo)號；而敗者樹的中間結(jié)點(diǎn)記錄的敗者的標(biāo)號。 勝者樹與敗者樹可以在log(n)的時間內(nèi)找到最值。任何一個葉子結(jié)點(diǎn)的值改變后，利用中間結(jié)點(diǎn)的信息，還是能夠快速地找到最值。在k路歸并排序中經(jīng)常用到。
一、勝者樹
勝者樹的一個優(yōu)點(diǎn)是，如果一個選手的值改變了，可以很容易地修改這棵勝者樹。只需要沿著從該結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑修改這棵二叉樹，而不必改變其他比賽的結(jié)果。下面是選擇一個最小的數(shù)字為最勝利者（見圖1所示），第一次把各個數(shù)組里面的第一個元素都放進(jìn)去，這是根據(jù)勝利樹的規(guī)則兩兩比較，得到最小的值，第一次弄完之后，就得出1數(shù)字是勝利的，也就是1是最小的。在下一次輸出第二小的數(shù)字時候，只需要把1所在的數(shù)組里面的元素加進(jìn)去，然后從葉子節(jié)點(diǎn)到根節(jié)點(diǎn)一直比較得出第二小的值，這樣就減少了很多次無用的比較（見圖2所示）。
圖 一 圖二
問題：有20個有序數(shù)組，每個數(shù)組有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
- * 轉(zhuǎn)載請注明出處，謝謝。
- *
- */
- #define N 10
- #define INF (1 << 31) - 1
- using namespace std;
-
- typedef struct Node{
- int which; //記錄是哪個子數(shù)組
- int index; //記錄是上個標(biāo)記數(shù)組的第幾個元素了
- int data; //記錄數(shù)組的元素
- }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);//為了代碼減少代碼量，我把每一次調(diào)用都調(diào)整整個樹，其實(shí)是不必要的，有興趣的用戶可以自己寫寫
- 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{//如果某個數(shù)組里面的數(shù)據(jù)處理完了，就把那個節(jié)點(diǎn)賦值為無窮大
- 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;
- //分配內(nèi)存空間
- for(i = 0; i < del; i++){
- a[i] = (int *)malloc(size * sizeof(int));
- }
-
- //初始化數(shù)組
- 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);
- }
-
- //利用勝利樹進(jìn)行處理
- winTree(a, del, size, size);
- return 0;
- }
二、敗者樹
敗者樹是勝者樹的一種變體。在敗者樹中，用父結(jié)點(diǎn)記錄其左右子結(jié)點(diǎn)進(jìn)行比賽的敗者，而讓勝者參加下一輪的比賽。敗者樹的根結(jié)點(diǎn)記錄的是敗者，需要加一個結(jié)點(diǎn)來記錄整個比賽的勝利者。采用敗者樹可以簡化重構(gòu)的過程。
