每日算法 — 使用java实现胜者树：k路归并的锦标赛选择与堆优化对比

引言

胜者树（Winner Tree），又称锦标赛树（Tournament Tree），是一种经典的完全二叉树结构，主要用于高效地从多个有序序列中选取最小（或最大）元素。它是k路归并排序和外部排序的核心数据结构，也是理解高级选择算法的重要基础。

与败者树（Loser Tree）相对应，胜者树在每个内部节点中保存的是左右子树比较的胜者。虽然败者树在某些场景下更新效率略高，但胜者树的结构更加直观，教学和理解成本更低。本文将深入讲解胜者树的原理，并用Java实现一个完整的k路归并系统。

核心思想

假设有 k 个已排序的数组需要合并为一个有序数组。朴素的做法是每次比较 k 个数组的当前首元素，选出最小者放入结果——这需要 O(k) 时间每次选择。胜者树通过构建一棵完全二叉树，将每次选择的时间降为 O(log k)。

胜者树的结构

• 叶子节点：存放 k 个有序序列的当前元素（以及序列编号）
• 内部节点：存放左右子节点比较的胜者（较小者）
• 根节点：存放全局最小元素

当某个叶子节点的元素被取出后，只需从该叶子向上更新到根节点，重新进行 O(log k) 次比较即可确定新的全局最小值。

算法实现

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Random;

/**
 * 胜者树实现类
 * 核心思想：用完全二叉树维护k个有序序列的当前最小值，每次选取和更新仅需O(log k)
 */
public class WinnerTree {

    // 叶子节点存储的数据：值和来源序列编号
    private static class Node {
        int value;      // 当前值
        int runId;      // 来源序列编号
        boolean valid;  // 是否有效（序列是否还有元素）

        Node(int value, int runId, boolean valid) {
            this.value = value;
            this.runId = runId;
            this.valid = valid;
        }
    }

    private Node[] leaves;      // 叶子节点数组
    private int[] tree;         // 内部节点数组，存储胜者的叶子索引
    private int k;              // 路数
    private int leafOffset;     // 叶子节点在tree中的起始偏移

    /**
     * 构建胜者树
     * @param initialValues 每个序列的初始首元素
     * @param valid 每个序列是否有效
     */
    public WinnerTree(int[] initialValues, boolean[] valid) {
        this.k = initialValues.length;
        // 计算叶子偏移：找到大于等于k的最小2的幂
        this.leafOffset = 1;
        while (leafOffset < k) {
            leafOffset <<= 1;
        }

        // 初始化叶子节点
        this.leaves = new Node[leafOffset * 2];
        for (int i = 0; i < leafOffset; i++) {
            if (i < k && valid[i]) {
                leaves[leafOffset + i] = new Node(initialValues[i], i, true);
            } else {
                // 用无穷大填充空叶子
                leaves[leafOffset + i] = new Node(Integer.MAX_VALUE, -1, false);
            }
        }

        // 构建内部节点
        this.tree = new int[leafOffset];
        buildTree();
    }

    /**
     * 自底向上构建胜者树
     */
    private void buildTree() {
        for (int i = leafOffset - 1; i > 0; i--) {
            tree[i] = compareAndSelect(i << 1, (i << 1) | 1);
        }
        tree[0] = tree[1]; // 根节点
    }

    /**
     * 比较两个叶子/内部节点，返回胜者的索引
     */
    private int compareAndSelect(int left, int right) {
        Node leftNode = leaves[left];
        Node rightNode = leaves[right];

        // 优先选择有效且值较小的节点
        if (!leftNode.valid) return right;
        if (!rightNode.valid) return left;
        return leftNode.value <= rightNode.value ? left : right;
    }

    /**
     * 获取当前全局最小值
     * @return 最小值对应的节点
     */
    public Node getWinner() {
        return leaves[tree[0]];
    }

    /**
     * 更新指定叶子节点，并自底向上重新调整胜者树
     * @param leafIndex 叶子节点索引（0-based）
     * @param newValue 新值
     * @param valid 是否有效
     */
    public void update(int leafIndex, int newValue, boolean valid) {
        int pos = leafOffset + leafIndex;
        leaves[pos].value = newValue;
        leaves[pos].valid = valid;

        // 自底向上更新
        pos >>= 1;
        while (pos > 0) {
            tree[pos] = compareAndSelect(pos << 1, (pos << 1) | 1);
            pos >>= 1;
        }
        tree[0] = tree[1];
    }

    /**
     * k路归并主方法：使用胜者树合并多个有序数组
     * @param runs 多个有序数组
     * @return 合并后的有序数组
     */
    public static int[] kWayMerge(int[][] runs) {
        int k = runs.length;
        int totalLen = 0;
        for (int[] run : runs) {
            totalLen += run.length;
        }

        int[] result = new int[totalLen];
        int[] indices = new int[k]; // 每个序列的当前读取位置

        // 收集每个序列的首元素
        int[] initialValues = new int[k];
        boolean[] valid = new boolean[k];
        for (int i = 0; i < k; i++) {
            if (runs[i].length > 0) {
                initialValues[i] = runs[i][0];
                valid[i] = true;
                indices[i] = 1;
            } else {
                valid[i] = false;
            }
        }

        // 构建胜者树
        WinnerTree wt = new WinnerTree(initialValues, valid);

        // 依次取出最小元素
        for (int i = 0; i < totalLen; i++) {
            Node winner = wt.getWinner();
            result[i] = winner.value;

            // 从获胜序列中读取下一个元素
            int runId = winner.runId;
            if (indices[runId] < runs[runId].length) {
                wt.update(runId, runs[runId][indices[runId]], true);
                indices[runId]++;
            } else {
                wt.update(runId, Integer.MAX_VALUE, false);
            }
        }

        return result;
    }

    /**
     * 使用优先队列实现k路归并，用于对比性能
     */
    public static int[] kWayMergeWithHeap(int[][] runs) {
        int totalLen = 0;
        for (int[] run : runs) totalLen += run.length;
        int[] result = new int[totalLen];

        PriorityQueue<Node> heap = new PriorityQueue<>(Comparator.comparingInt(n -> n.value));
        int[] indices = new int[runs.length];

        for (int i = 0; i < runs.length; i++) {
            if (runs[i].length > 0) {
                heap.offer(new Node(runs[i][0], i, true));
                indices[i] = 1;
            }
        }

        int idx = 0;
        while (!heap.isEmpty()) {
            Node min = heap.poll();
            result[idx++] = min.value;
            if (indices[min.runId] < runs[min.runId].length) {
                heap.offer(new Node(runs[min.runId][indices[min.runId]], min.runId, true));
                indices[min.runId]++;
            }
        }

        return result;
    }

    /**
     * 主程序：演示胜者树在k路归并中的应用
     */
    public static void main(String[] args) {
        // 构造5个有序数组
        int[][] runs = {
            {1, 5, 9, 13, 17},
            {2, 6, 10, 14, 18},
            {3, 7, 11, 15, 19},
            {4, 8, 12, 16, 20},
            {0, 21, 22, 23, 24}
        };

        System.out.println("=== k路归并演示 ===");
        System.out.println("输入序列:");
        for (int i = 0; i < runs.length; i++) {
            System.out.println("  序列 " + i + ": " + Arrays.toString(runs[i]));
        }

        int[] merged = kWayMerge(runs);
        System.out.println("\n归并结果: " + Arrays.toString(merged));

        // 大规模性能对比
        System.out.println("\n=== 大规模性能对比：胜者树 vs 优先队列 ===");
        int k = 64; // 64路归并
        int runSize = 10000;
        int[][] largeRuns = new int[k][runSize];
        Random random = new Random(42);

        for (int i = 0; i < k; i++) {
            for (int j = 0; j < runSize; j++) {
                largeRuns[i][j] = random.nextInt(1000000);
            }
            Arrays.sort(largeRuns[i]);
        }

        // 胜者树
        long start1 = System.currentTimeMillis();
        int[] result1 = kWayMerge(largeRuns);
        long time1 = System.currentTimeMillis() - start1;

        // 优先队列
        long start2 = System.currentTimeMillis();
        int[] result2 = kWayMergeWithHeap(largeRuns);
        long time2 = System.currentTimeMillis() - start2;

        System.out.println("路数: " + k + ", 每路大小: " + runSize);
        System.out.println("胜者树耗时: " + time1 + "ms");
        System.out.println("优先队列耗时: " + time2 + "ms");
        System.out.println("结果一致性: " + (Arrays.equals(result1, result2) ? "通过" : "失败"));

        // 验证排序
        boolean sorted = true;
        for (int i = 1; i < result1.length; i++) {
            if (result1[i] < result1[i - 1]) {
                sorted = false;
                break;
            }
        }
        System.out.println("排序验证: " + (sorted ? "通过" : "失败"));
    }
}

算法详解

树的结构映射

胜者树使用数组模拟完全二叉树。设叶子偏移为 leafOffset（大于等于 k 的最小2的幂）：

内部节点: tree[0] (根) ... tree[leafOffset-1]
叶子节点: leaves[leafOffset] ... leaves[2*leafOffset-1]

例如 k=5 时，leafOffset=8，树的结构为：

              tree[0]=根
                 |
              tree[1]
            /        \
        tree[2]    tree[3]
       /      \    /      \
    tree[4] tree[5] tree[6] tree[7]
    (实际为leaves[8..15])

更新流程

当某个序列的当前元素被取出后：
1. 更新对应叶子节点为序列的下一个元素（或标记为无效）
2. 从该叶子节点的父节点开始向上遍历
3. 每个内部节点重新比较左右子节点，选出新的胜者
4. 根节点始终保存全局最小值的索引

复杂度分析

胜者树 vs 败者树

败者树更新时不需要与兄弟节点比较（只需与父节点存储的败者比较），因此比较次数略少。但胜者树的代码更直观，在 k 不太大的场景下性能差异可以忽略。

实际应用场景

胜者树的核心应用场景是外部排序：

1. 数据库系统：当数据量超过内存容量时，需要分块排序后多路归并
2. 大数据处理：MapReduce 等框架中的归并阶段
3. 日志合并：多个有序日志流按时间戳合并
4. k路有序集合合并：如搜索引擎中合并多个倒排索引的 posting list

总结

胜者树是理解”锦标赛选择”思想的经典数据结构。它将 k 路选择问题从 O(k) 优化到 O(log k)，是外部排序不可或缺的基石。本文的Java实现展示了如何用数组模拟完全二叉树，以及如何在 k 路归并场景中发挥胜者树的性能优势。

与优先队列相比，胜者树具有更好的缓存局部性（数组顺序访问 vs 堆的跳跃访问），在 k 较大时可能表现出更好的实际性能。理解胜者树，不仅能帮助你掌握 k 路归并的实现，更能深化对完全二叉树在算法中应用的理解。