每日算法 — 使用java实现左偏树：可并堆与优先队列合并

引言

在算法竞赛和工程实践中，优先队列（堆）是一种极为常用的数据结构。然而，标准的二叉堆不支持高效的两个堆合并操作——合并两个二叉堆需要 O(n) 的时间。左偏树（Leftist Tree）是一种可并堆（Mergeable Heap），它能在 O(log n) 时间内完成两个堆的合并，同时还能高效支持插入、删除最值等操作。本文将用 Java 完整实现左偏树，并展示其在多路归并等场景中的应用。

左偏树的核心概念

什么是左偏树

左偏树是一种满足堆性质（大根堆或小根堆）的二叉树，同时它还满足左偏性质：对于任意节点，其左儿子的零距离（null path length）不小于右儿子的零距离。

零距离（NPL, Null Path Length）

零距离是指从一个节点到其最近的空子节点的距离。具体来说：
– 空节点的 NPL 为 -1
– 叶子节点的 NPL 为 0
– 非叶子节点的 NPL = min(左儿子NPL, 右儿子NPL) + 1

左偏性质

对于左偏树中的每个节点，都有：

npl(leftChild) >= npl(rightChild)

这一性质保证了树的右路径（从根节点一直往右走的路径）长度被限制在 O(log n) 内，从而使合并操作能在 O(log n) 时间内完成。

算法核心操作

合并（Merge）

合并是左偏树最核心的操作，其他操作都可以基于合并实现：

1. 若其中一个堆为空，返回另一个堆
2. 比较两个堆的根节点，将值较大的（假设是大根堆）作为新根
3. 递归合并新根的右子树与另一个堆
4. 维护左偏性质：若左子树的NPL小于右子树，交换左右子树
5. 更新当前节点的NPL

基于合并的其他操作

• 插入：将新节点视为单节点堆，与原堆合并 — O(log n)
• 删除最大值：合并根节点的左右子树 — O(log n)
• 获取最大值：直接读取根节点值 — O(1)

Java 完整实现

import java.util.*;

/**
 * 左偏树（Leftist Tree）实现 —— 可并堆
 * 支持 O(log n) 时间复杂度的堆合并操作
 */
public class LeftistTree {

    /**
     * 左偏树节点
     */
    static class Node {
        int value;          // 节点值
        int npl;            // 零距离（Null Path Length）
        Node left;          // 左子节点
        Node right;         // 右子节点

        public Node(int value) {
            this.value = value;
            this.npl = 0;   // 新节点的NPL初始为0
            this.left = null;
            this.right = null;
        }
    }

    private Node root;      // 根节点
    private int size;       // 堆中元素数量

    public LeftistTree() {
        this.root = null;
        this.size = 0;
    }

    /**
     * 获取堆的大小
     */
    public int size() {
        return size;
    }

    /**
     * 判断堆是否为空
     */
    public boolean isEmpty() {
        return root == null;
    }

    /**
     * 获取最大值（大根堆）
     * 时间复杂度：O(1)
     */
    public Integer peekMax() {
        return root == null ? null : root.value;
    }

    /**
     * 合并两个左偏树
     * 这是左偏树的核心操作，时间复杂度：O(log n)
     * @param h1 第一个堆的根
     * @param h2 第二个堆的根
     * @return 合并后的堆的根
     */
    private Node merge(Node h1, Node h2) {
        // 若其中一个为空，返回另一个
        if (h1 == null) return h2;
        if (h2 == null) return h1;

        // 确保 h1 的值较大（大根堆）
        if (h1.value < h2.value) {
            Node temp = h1;
            h1 = h2;
            h2 = temp;
        }

        // 递归合并 h1 的右子树与 h2
        h1.right = merge(h1.right, h2);

        // 维护左偏性质：左子树的NPL应大于等于右子树
        int leftNpl = (h1.left == null) ? -1 : h1.left.npl;
        int rightNpl = (h1.right == null) ? -1 : h1.right.npl;

        if (leftNpl < rightNpl) {
            // 交换左右子树
            Node temp = h1.left;
            h1.left = h1.right;
            h1.right = temp;
        }

        // 更新当前节点的NPL
        h1.npl = (h1.right == null) ? 0 : h1.right.npl + 1;

        return h1;
    }

    /**
     * 将另一个左偏树合并到当前堆
     */
    public void merge(LeftistTree other) {
        if (other == null || other.root == null) return;
        this.root = merge(this.root, other.root);
        this.size += other.size;
        other.root = null;
        other.size = 0;
    }

    /**
     * 插入一个新元素
     * 将新元素视为单节点堆，与当前堆合并
     * 时间复杂度：O(log n)
     */
    public void insert(int value) {
        Node newNode = new Node(value);
        this.root = merge(this.root, newNode);
        this.size++;
    }

    /**
     * 删除并返回最大值
     * 合并根节点的左右子树
     * 时间复杂度：O(log n)
     */
    public Integer extractMax() {
        if (root == null) return null;

        int maxValue = root.value;
        this.root = merge(root.left, root.right);
        this.size--;
        return maxValue;
    }

    /**
     * 中序遍历（用于调试和验证）
     */
    public void inorderTraversal() {
        System.out.print("Inorder: ");
        inorder(root);
        System.out.println();
    }

    private void inorder(Node node) {
        if (node == null) return;
        inorder(node.left);
        System.out.print(node.value + " ");
        inorder(node.right);
    }

    /**
     * 验证左偏性质（用于调试）
     */
    public boolean validateLeftistProperty() {
        return validateNode(root);
    }

    private boolean validateNode(Node node) {
        if (node == null) return true;

        int leftNpl = (node.left == null) ? -1 : node.left.npl;
        int rightNpl = (node.right == null) ? -1 : node.right.npl;

        // 检查左偏性质
        if (leftNpl < rightNpl) {
            System.err.println("Leftist property violated at node " + node.value);
            return false;
        }

        // 检查NPL计算是否正确
        int expectedNpl = (node.right == null) ? 0 : node.right.npl + 1;
        if (node.npl != expectedNpl) {
            System.err.println("NPL incorrect at node " + node.value);
            return false;
        }

        return validateNode(node.left) && validateNode(node.right);
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("LeftistTree(size=").append(size).append("): ");
        List<Integer> elements = new ArrayList<>();
        collectElements(root, elements);
        sb.append(elements);
        return sb.toString();
    }

    private void collectElements(Node node, List<Integer> list) {
        if (node == null) return;
        list.add(node.value);
        collectElements(node.left, list);
        collectElements(node.right, list);
    }

    // ==================== 应用示例 ====================

    /**
     * K路归并：合并K个已排序的数组
     * 使用左偏树维护K个数组的当前最小值
     */
    public static int[] kWayMerge(int[][] sortedArrays) {
        int k = sortedArrays.length;
        int totalLen = 0;
        for (int[] arr : sortedArrays) totalLen += arr.length;

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

        // 自定义比较器，用于小根堆
        // 这里我们使用多个单节点左偏树实现优先队列
        PriorityQueue<Element> pq = new PriorityQueue<>(Comparator.comparingInt(e -> e.value));

        // 初始化：将每个数组的第一个元素加入优先队列
        for (int i = 0; i < k; i++) {
            if (sortedArrays[i].length > 0) {
                pq.offer(new Element(sortedArrays[i][0], i));
            }
        }

        int pos = 0;
        while (!pq.isEmpty()) {
            Element min = pq.poll();
            result[pos++] = min.value;

            int arrIdx = min.arrayIndex;
            indices[arrIdx]++;

            if (indices[arrIdx] < sortedArrays[arrIdx].length) {
                pq.offer(new Element(sortedArrays[arrIdx][indices[arrIdx]], arrIdx));
            }
        }

        return result;
    }

    static class Element {
        int value;
        int arrayIndex;

        Element(int value, int arrayIndex) {
            this.value = value;
            this.arrayIndex = arrayIndex;
        }
    }

    /**
     * 演示：多个左偏树的合并操作
     */
    public static void demoMerge() {
        System.out.println("=== Leftist Tree Demo ===\n");

        // 创建第一个堆
        LeftistTree heap1 = new LeftistTree();
        heap1.insert(10);
        heap1.insert(20);
        heap1.insert(5);
        heap1.insert(30);
        System.out.println("Heap1: " + heap1);
        System.out.println("Heap1 max: " + heap1.peekMax());

        // 创建第二个堆
        LeftistTree heap2 = new LeftistTree();
        heap2.insert(15);
        heap2.insert(25);
        heap2.insert(8);
        System.out.println("Heap2: " + heap2);

        // 合并两个堆
        heap1.merge(heap2);
        System.out.println("After merge: " + heap1);
        System.out.println("Merged heap size: " + heap1.size());
        System.out.println("Valid leftist property: " + heap1.validateLeftistProperty());

        // 依次取出最大值
        System.out.print("Extract max sequence: ");
        while (!heap1.isEmpty()) {
            System.out.print(heap1.extractMax() + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        demoMerge();

        // K路归并示例
        System.out.println("\n=== K-Way Merge Demo ===");
        int[][] arrays = {
            {1, 4, 7, 10},
            {2, 5, 8, 11},
            {3, 6, 9, 12}
        };
        int[] merged = kWayMerge(arrays);
        System.out.println("Merged array: " + Arrays.toString(merged));
    }
}

算法复杂度分析

左偏树 vs 其他堆结构

左偏树在实现复杂度与性能之间取得了良好的平衡，特别适合需要频繁合并堆的场景。

应用场景

左偏树在以下场景中表现出色：

• K路归并：合并多个有序序列时，用左偏树维护各序列当前最小值
• 动态图算法：如最小生成树的动态维护，需要合并连通分量的边集
• 并行计算：多线程环境下各自维护局部堆，最后合并结果
• 哈夫曼编码优化：在批量构建哈夫曼树时，可并行构建子树再合并

总结

左偏树通过巧妙的左偏性质，将堆合并的时间复杂度从 O(n) 降低到 O(log n)。其结构简单、实现优雅，是处理可合并堆问题的理想选择。掌握左偏树，将帮助你在需要频繁合并优先队列的场景中写出更高效的代码。