敗者樹多路歸併完整實現：C語言代碼詳解與優化

編輯：關於C語言

前言

敗者樹 是外部排序中多路歸併的經典資料結構，時間複雜度 O(log k) 選出最小元素（k 為路數）。本文提供完整 C 語言實現，含樹建構、歸併主迴圈、哨兵值處理，並分析關鍵細節與改進方向。

問題設定

k 個已排序序列，每序列長度 n
歸併為單一有序序列
本實現假設 k 為 2 的冪（完全二元樹葉子數），非 2 的冪時向上取最接近的 2 的冪
每序列末尾附加 MAX_BIG (999999999) 作為哨兵，簡化終止判斷

資料結構設計


typedef struct wrap_data {
    int offset;      // 當前序列讀取位置
    int path;        // 葉子索引（0~k-1）
    int *data;       // 指向序列陣列
} wrap_data;

wrap_data **tree;    // 敗者樹節點陣列（指標陣列）
int tree_size;       // 總節點數 = 2 * leaf_count

核心函式：向上調整


/* 從葉子索引 num 向根調整，返回新勝者 */
wrap_data *up(int num) {
    int i = num, j;
    wrap_data *first, *second = tree[i];

    while (i) {
        j = i / 2;               // 父節點
        first = tree[j];

        if (!first) {            // 父節點空 → 直接提升
            tree[j] = second;
            if (!j) return second;  // 到達根
            return NULL;         // 非根需繼續向上
        }

        if (first->path == second->path) {
            i = j;               // 同一路徑，繼續向上
        }
        else if (*(second->data + second->offset) >
                 *(first->data + first->offset)) {
            tree[j] = second;    // second 較大（敗者），存入父節點
            second = first;      // 勝者繼續向上比較
            i = j;
        }
        else {
            i = j;               // first 勝出，second 繼續向上
        }
    }
    return second;               // 最終勝者
}

主程式流程


#define PATH 4          // 路數
#define LENGTH 10       // 每序列長度
#define MAX_BIG 999999999

int main() {
    wrap_data *result;
    int i, j, k;
    wrap_data seq[PATH] = {0};

    /* 1. 分配敗者樹陣列 */
    tree_size = 2 * choosevec(PATH);  // 向上取 2 的冪葉子數
    tree = (wrap_data **)calloc(tree_size, sizeof(wrap_data *));

    /* 2. 初始化 4 個測試序列 */
    for (i = 0; i < PATH; i++) {
        seq[i].data = (int *)calloc(LENGTH, sizeof(int));
        seq[i].offset = 0;
        seq[i].path = i;
        for (j = 0; j < LENGTH; j++)
            seq[i].data[j] = (i * i + j) % 40;  // 生成有序測試資料
        seq[i].data[LENGTH-1] = MAX_BIG;        // 哨兵
    }

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

    /* 4. 建立初始敗者樹：葉子節點填入樹底層 */
    k = tree_size / 2;  // 第一個葉子位置
    for (i = 0; i < PATH; i++) tree[k + i] = &seq[i];

    /* 5. 自底向上建樹 */
    for (i = 0; i < PATH; i++) {
        result = up(k + i);
        if (result) break;  // 根節點產生
    }

    /* 6. 歸併主迴圈 */
    while (result) {
        int val = *(result->data + result->offset);
        if (val == MAX_BIG) break;  // 所有序列耗盡
        printf("%d ", val);
        result->offset++;           // 該序列前進
        result = up(result->path + k);  // 重新調整
    }
    printf("\n");

    /* 釋放記憶體略 */
    return 0;
}

輔助函式：葉子數計算


int choosevec(int path) {
    if (path <= 4) return 4;
    if (path <= 8) return 8;
    if (path <= 16) return 16;
    return 32;
}

關鍵邏輯解析

步驟	操作	說明
樹大小	`2 * leaf_count`	完全二元樹節點數，索引 1 為根，葉子從 `leaf_count` 開始
初始建樹	依序 `up(leaf_i)`	每次插入一個葉子向上調整，最後根節點存放全域勝者
勝者輸出	根節點指向的序列輸出當前元素	輸出後 `offset++` 推進該序列
重新調整	`up(winner_path + leaf_base)`	從該葉子重新向上比較，更新路徑上所有敗者節點
終止條件	輸出值 == `MAX_BIG`	哨兵值保證所有序列耗盡時同步終止

輸出範例

原始序列：
0 1 2 3 4 5 6 7 8 999999999
1 2 3 4 5 6 7 8 9 999999999
4 5 6 7 8 9 10 11 12 999999999
9 10 11 12 13 14 15 16 17 999999999

歸併結果：
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