勝者樹與敗者樹：多路歸并排序的利器

“勝者樹”（Winner Tree）和“敗者樹”（Loser Tree）都是完全二叉樹結構，前者廣泛用于多路歸并排序和優先級選擇問題中，尤其是在歸并排序器、堆式選擇算法中有重要應用，后者常用于多路歸并排序中（例如外部排序），是**勝者樹（Winner Tree）**的一種變體。

---

1 勝者樹簡介

1.1 定義

• 勝者樹是一棵完全二叉樹，每個葉子結點表示一個選手（或者一個序列當前值），
• 每個非葉子節點存儲當前兩名子選手的勝者（較小者）索引。
• 根節點最終存儲的是所有選手中最小值的索引（即冠軍/勝者）。

勝者樹常用于：

• ? 多路歸并排序
• ? 外部排序（歸并多個文件）
• ? 堆選擇算法（優先隊列）
• ? 歸并K個有序序列/流式合并

---

1.2 勝者樹結構與原理

1.2.1 構造流程

假設我們要從 k 個已排好序的序列中進行歸并，每個序列的當前元素是一個“選手”：

1. 葉子結點存放 k 個選手的索引（或值）。
2. 相鄰兩個選手進行比較，較小者（勝者）進入上層節點。
3. 一直遞歸比較，直到根節點，表示最終勝者。
4. 內部節點都記錄每次比賽的勝者索引。

1.2.2 歸并過程

每輪輸出根節點對應的值（最小值），然后用該“選手”所在的序列下一項替代，并自底向上更新路徑即可，時間復雜度為 O(log k)。

---

2 敗者樹簡介

2.1 背景場景

假設你有多個已經排好序的數組（或文件），想把它們合并成一個大的有序序列。這就叫多路歸并。當有很多路時（比如上百個文件），直接線性比較效率很低，敗者樹可以高效解決這個問題。

2.2 基本定義

• 敗者樹是一棵完全二叉樹，用于記錄多路歸并中每輪比較的失敗者（較大者）。
• 樹的內部結點記錄的是敗者，而不是勝者。
• 整棵樹的根節點并不表示最小值，而是指向在當前輪比賽中被打敗的選手。

敗者樹常用于：

• 外部排序中的多路歸并排序
• 優先級選擇器（類似小根堆）
• K 路歸并排序器（如歸并 16 個文件，找到最小項）

2.3 敗者樹結構和原理

假設有 k 個已排好序的輸入序列，敗者樹的構建步驟如下：

2.3.1 樹的構造（初始建樹）

1. 將 k 個選手（對應于每個輸入序列的第一個元素）作為葉子節點。
2. 比較相鄰兩個選手，將較大的（敗者）向上傳遞，較小的（勝者）繼續往上走。
3. 最后勝者會落在“勝者路徑”上，沿路的結點記錄被其打敗的對手（即敗者）。
4. 樹的根并不是最終勝者，而是最后一次比較的敗者。

2.3.2 查詢和更新

• 每次輸出最小元素（勝者）。
• 然后將該序列推進一個新元素，再從該葉子節點重新進行比較并更新路徑，時間復雜度是 O(log k)。

---

3 勝者樹 vs 敗者樹

特性	勝者樹	敗者樹
內部節點記錄	勝者（最小）	敗者（較大）
根節點	勝者（最小值）	敗者
插入/更新效率	O(log k)	O(log k)
查詢最小值	直接查根	查 tree[0] 對應葉子
代碼邏輯復雜度	相對較簡單	相對復雜
實際使用	優先隊列、歸并排序等	多路歸并排序優化

---

4 勝者樹示例代碼

#include <iostream>
#include <vector>
#include <climits>
#include <cassert>class WinnerTree {
private:int k;std::vector<int> tree;   // 完全二叉樹結構，1-based，tree[1] 是根，tree[0] 存儲最終 winner 索引std::vector<int> leaves; // 葉子數組，存儲實際數據public:WinnerTree(const std::vector<int>& init) : k(init.size()), leaves(init) {// 樹大小需要 2*k（包含葉子和內部節點）tree.resize(2 * k, -1);build();}void build() {// 初始化葉子節點（從 tree[k] 到 tree[2k - 1]）for (int i = 0; i < k; ++i) {tree[k + i] = i;}// 從底向上構建 winner treefor (int i = k - 1; i > 0; --i) {int left = tree[i * 2];int right = tree[i * 2 + 1];if (right == -1 || (left != -1 && leaves[left] <= leaves[right])) {tree[i] = left;} else {tree[i] = right;}}tree[0] = tree[1]; // winner 存到 tree[0]}void adjust(int leafIdx) {int pos = k + leafIdx;while (pos > 1) {int sibling = (pos % 2 == 0) ? pos + 1 : pos - 1;int parent = pos / 2;int left = tree[parent * 2];int right = (parent * 2 + 1 < (int)tree.size()) ? tree[parent * 2 + 1] : -1;if (right == -1 || (left != -1 && leaves[left] <= leaves[right])) {tree[parent] = left;} else {tree[parent] = right;}pos = parent;}tree[0] = tree[1];}int winner() const {return tree[0];}int value(int i) const {return leaves[i];}void popAndReplace(int idx, int newValue) {leaves[idx] = newValue;adjust(idx);}
};int main() {std::vector<int> init = {3, 6, 1, 9};WinnerTree wt(init);for (int i = 0; i < 4; ++i) {int win = wt.winner();std::cout << wt.value(win) << " ";wt.popAndReplace(win, INT_MAX); // 替換為無窮大，模擬歸并過程}return 0;
}

輸出結果：

1 3 6 9

---

5 敗者樹代碼示例

#include <iostream>
#include <vector>
#include <climits>class LoserTree {
private:int k;std::vector<int> tree;   // 內部節點，size k，tree[0]為勝者葉子編號std::vector<int> leaves; // 葉子值，size kpublic:explicit LoserTree(const std::vector<int>& input) : k((int)input.size()), tree(k, -1), leaves(input) {build();}void build() {// 初始化所有內部節點為-1for (int i = 0; i < k; ++i) tree[i] = -1;for (int i = k - 1; i >= 0; --i) {adjust(i);}}void adjust(int s) {int t = s;int parent = (s + k) / 2;while (parent > 0) {if (parent >= k) {std::cerr << "ERROR: parent index out of range: " << parent << std::endl;std::cerr << "k = " << k << std::endl;std::exit(1);}// debug輸出當前比較的節點和值// std::cout << "Adjust: parent = " << parent << ", t = " << t//           << ", leaves[t] = " << leaves[t]//           << ", tree[parent] = " << tree[parent]//           << ", leaves[tree[parent]] = " << (tree[parent] == -1 ? INT_MAX : leaves[tree[parent]])//           << std::endl;if (tree[parent] == -1 || leaves[t] < leaves[tree[parent]]) {std::swap(t, tree[parent]);}parent /= 2;}tree[0] = t;}int winner() const { return tree[0]; }int value(int idx) const {if (idx < 0 || idx >= k) return INT_MAX;return leaves[idx];}void popAndReplace(int idx, int newVal) {if (idx < 0 || idx >= k) {std::cerr << "popAndReplace: idx out of range: " << idx << std::endl;return;}leaves[idx] = newVal;adjust(idx);}
};int main() {std::vector<int> input = {20, 15, 30, 10};LoserTree lt(input);std::cout << "Winner index: " << lt.winner() << std::endl;std::cout << "Winner value: " << lt.value(lt.winner()) << std::endl;lt.popAndReplace(lt.winner(), 25);std::cout << "After replacement:" << std::endl;std::cout << "Winner index: " << lt.winner() << std::endl;std::cout << "Winner value: " << lt.value(lt.winner()) << std::endl;return 0;
}

---

6 總結

勝者樹：

優點	描述
? 高效	查詢最小值時間復雜度 O(1)，更新 O(log k)
? 結構清晰	比堆更適合用于 K 路歸并選擇
? 實用性強	外排序、文件合并、流式排序等場景常見

敗者樹：

• 敗者樹是一種適合多路歸并排序的高效數據結構。
• 每次找最小值和更新的操作是 O(log k)。
• 通常用于數據量過大、需要外部存儲的場景（如磁盤文件排序）。
• 實現比堆略復雜，但效率在多路歸并時更優。