您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C >> 關於C

敗者樹實現多路歸並：C 語言完整實作與圖解

編輯：關於C

什麼是敗者樹？

敗者樹是完全二叉樹的變體，**葉節點存放各有序序列的當前元素，內部節點存放「較大者」（敗者）的索引**。根節點永遠指向全局最小元素（勝者）。取出根對應元素後，從該葉節點重新比較向上更新，時間複雜度 O(log k)（k 為序列數），優於堆的常數因子。

資料結構設計


#define MAX_BIG 999999999  // 哨兵值，標記序列結束

typedef struct {
    int* data;      // 指向有序序列陣列
    int offset;     // 當前讀取位置
    int path;       // 葉節點索引 (0~k-1)
} WrapData;

WrapData** tree;    // 敗者樹節點陣列 (大小 2 * 次方數)
int treeSize;       // 實際節點數
int k;              // 序列數

核心函數：向上調整 `up`

從葉節點 num 向根比較更新，回傳新勝者指標：


WrapData* up(int num) {
    int i = num;
    WrapData* second = tree[i];  // 當前挑戰者

    while (i) {
        int j = i / 2;           // 父節點
        WrapData* first = tree[j]; // 父節點現存勝者

        if (!first) {            // 父節點為空 → 直接佔據
            tree[j] = second;
            if (!j) return second; // 到達根
            else return NULL;      // 中途非根，繼續下一輪
        }

        // 比較當前元素值
        int valSecond = second->data[second->offset];
        int valFirst  = first->data[first->offset];

        if (first->path == second->path) {
            i = j;  // 同一序列，繼續向上
        } else if (valSecond > valFirst) {
            // second 是敗者 → 父節點保留 first，second 繼續向上挑戰
            tree[j] = second;
            second = first;
            i = j;
        } else {
            // first 是敗者 → 父節點保留 second，first 繼續向上（這裡 first 已在樹中，無需動作）
            i = j;
        }
    }
    return second;  // 根節點勝者
}

初始化與建樹


int chooseVec(int k) {  // 計算大於等於 k 的最小 2 次方
    if (k <= 4) return 4;
    if (k <= 8) return 8;
    if (k <= 16) return 16;
    return 32;
}

void initLoserTree(WrapData seqs[], int k) {
    ::k = k;
    int vec = chooseVec(k);
    treeSize = 2 * vec;
    tree = calloc(treeSize, sizeof(WrapData*));

    // 葉節點填入序列資訊
    int leafStart = treeSize / 2;
    for (int i = 0; i < k; i++) {
        tree[leafStart + i] = &seqs[i];
    }

    // 自底向上建樹
    WrapData* winner = NULL;
    for (int i = 0; i < k; i++) {
        winner = up(leafStart + i);
        if (winner) break;  // 首次到達根即可
    }
}

歸並主迴圈


void merge(WrapData seqs[], int k, int len) {
    initLoserTree(seqs, k);

    WrapData* winner = tree[0];  // 根節點勝者
    while (winner) {
        int val = winner->data[winner->offset];
        if (val == MAX_BIG) break;  // 所有序列耗盡

        printf("%d ", val);  // 輸出最小元素
        winner->offset++;     // 該序列前進

        // 從該葉節點重新調整
        winner = up(winner->path + treeSize / 2);
    }
    printf("\n");
}

完整測試程式


#include 
#include 

#define PATH 4
#define LENGTH 10
#define MAX_BIG 999999999

// ... 上述結構與函數定義 ...

int main() {
    WrapData a[PATH] = {0};

    // 生成 4 條測試序列
    for (int i = 0; i < PATH; i++) {
        a[i].data = calloc(LENGTH, sizeof(int));
        a[i].offset = 0;
        a[i].path = i;
        for (int j = 0; j < LENGTH - 1; j++) {
            a[i].data[j] = (i * i + j) % 40;  // 產生 0~39 亂數
        }
        a[i].data[LENGTH - 1] = MAX_BIG;  // 哨兵
    }

    // 列印原始序列
    for (int i = 0; i < PATH; i++) {
        for (int j = 0; j < LENGTH; j++) printf("%d ", a[i].data[j]);
        printf("\n");
    }

    merge(a, PATH, LENGTH);

    // 釋放記憶體
    for (int i = 0; i < PATH; i++) free(a[i].data);
    free(tree);
    return 0;
}

執行結果示例

輸入序列:
0 1 2 3 4 5 6 7 8 MAX_BIG
1 2 3 4 5 6 7 8 9 MAX_BIG
4 5 6 7 8 9 10 11 12 MAX_BIG
9 10 11 12 13 14 15 16 17 MAX_BIG

輸出歸並結果:
0 1 1 2 2 3 3 4 4 4 5 5 5 6 6 6 7 7 7 8 8 8 9 9 9 10 10 11 11 12 12 13 14 15 16 17