每日算法 — 使用java实现配对堆：可并堆的高效合并与摊还分析

问题背景

在图论算法中，可并堆（Mergeable Heap）是一类支持高效合并操作的数据结构。经典应用包括：
– Dijkstra最短路径算法中的优先队列
– Prim最小生成树算法
– 哈夫曼编码
– 任务调度系统

传统二叉堆的 insert、deleteMin、decreaseKey 操作都是 $O(\log n)$，但合并两个堆需要 $O(n)$ 时间。可并堆（如二项堆、斐波那契堆、配对堆）将合并优化到 $O(1)$（均摊）。

配对堆（Pairing Heap）由Fredman、Sedgewick、Sleator和Tarjan于1986年提出。它在实际运行中表现出与斐波那契堆相当甚至更优的性能，同时实现复杂度远低于斐波那契堆，是现代算法竞赛和工业界的首选可并堆之一。

核心原理

结构特点

配对堆是一棵多叉树，满足堆性质：每个节点的值不大于（或不小于）其子节点的值。

• 根节点：存储堆中的最小值
• 子节点：以双向循环链表组织，便于快速合并和删除

核心操作

1. 合并（Merge）

将两个配对堆合并为一个。比较两个堆的根节点，将根较大的堆作为根较小的堆的子树。

merge(A, B):
    if A is null: return B
    if B is null: return A
    if A.val > B.val: swap(A, B)
    // A.val <= B.val，将B作为A的子节点
    B.next = A.child
    if A.child != null: A.child.prev = B
    A.child = B
    B.prev = A
    return A

时间复杂度：$O(1)$

2. 插入（Insert）

将单个元素视为一个单节点堆，与原堆合并。

时间复杂度：$O(1)$

3. 删除最小值（DeleteMin）

删除根节点后，需要对根的所有子节点重新合并。配对堆采用两趟合并法（Two-pass Merging）：

• 第一趟（从左到右配对）：将子节点从左到右两两配对合并
• 第二趟（从右到左累积）：将配对合并的结果从右到左依次合并

时间复杂度：$O(\log n)$ 均摊

4. 减小键值（DecreaseKey）

将某节点的值减小后，如果破坏了堆性质，直接将该节点从父节点处切断，然后与原堆合并。

时间复杂度：$O(1)$ 均摊

Java实现

import java.util.*;

/**
 * 配对堆（Pairing Heap）实现
 * 支持O(1)插入/合并，O(log n)均摊删除最小值
 * 基于多叉树+双向链表结构
 */
public class PairingHeap<T extends Comparable<T>> {

    /**
     * 节点类：多叉树节点，子节点用双向循环链表组织
     */
    private static class Node<T> {
        T key;                  // 键值
        Node<T> parent;         // 父节点
        Node<T> child;          // 第一个子节点
        Node<T> next;           // 右兄弟
        Node<T> prev;           // 左兄弟（或父节点，如果是第一个子节点）

        Node(T key) {
            this.key = key;
            this.parent = null;
            this.child = null;
            this.next = this;   // 循环链表初始化
            this.prev = this;
        }
    }

    private Node<T> root;       // 根节点
    private int size;           // 节点总数

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

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

    /**
     * 获取堆中元素个数
     */
    public int size() {
        return size;
    }

    /**
     * 查看最小值（不删除）
     */
    public T findMin() {
        if (root == null) return null;
        return root.key;
    }

    /**
     * 合并两个配对堆
     * 时间复杂度：O(1)
     */
    public void merge(PairingHeap<T> other) {
        if (other == null || other.root == null) return;
        this.root = mergeRoots(this.root, other.root);
        this.size += other.size;
        other.root = null;
        other.size = 0;
    }

    /**
     * 合并两棵子树，返回新根
     */
    private Node<T> mergeRoots(Node<T> a, Node<T> b) {
        if (a == null) return b;
        if (b == null) return a;

        // 确保 a.key <= b.key
        if (a.key.compareTo(b.key) > 0) {
            Node<T> tmp = a;
            a = b;
            b = tmp;
        }

        // 将 b 作为 a 的子节点（插入到子节点链表头部）
        if (a.child == null) {
            a.child = b;
            b.parent = a;
            b.next = b;
            b.prev = b;
        } else {
            // 将b插入到a.child的循环链表中
            Node<T> firstChild = a.child;
            b.next = firstChild;
            b.prev = firstChild.prev;
            firstChild.prev.next = b;
            firstChild.prev = b;
            b.parent = a;
            a.child = b;  // b成为新的第一个子节点
        }

        return a;
    }

    /**
     * 插入元素
     * 时间复杂度：O(1)
     */
    public void insert(T key) {
        Node<T> newNode = new Node<>(key);
        if (root == null) {
            root = newNode;
        } else {
            root = mergeRoots(root, newNode);
        }
        size++;
    }

    /**
     * 删除并返回最小值
     * 时间复杂度：O(log n) 均摊
     */
    public T deleteMin() {
        if (root == null) return null;

        T minKey = root.key;
        Node<T> firstChild = root.child;

        // 根节点被删除
        root.child = null;
        root = null;
        size--;

        if (firstChild == null) {
            root = null;
            return minKey;
        }

        // 断开循环链表，收集所有子节点
        List<Node<T>> children = new ArrayList<>();
        Node<T> cur = firstChild;
        do {
            Node<T> next = cur.next;
            cur.parent = null;
            cur.next = cur;
            cur.prev = cur;
            children.add(cur);
            cur = next;
        } while (cur != firstChild);

        // 两趟合并法
        root = twoPassMerge(children);

        return minKey;
    }

    /**
     * 两趟合并法
     * 第一趟：从左到右两两配对合并
     * 第二趟：从右到左依次合并结果
     */
    private Node<T> twoPassMerge(List<Node<T>> nodes) {
        if (nodes.isEmpty()) return null;
        if (nodes.size() == 1) return nodes.get(0);

        // 第一趟：从左到右两两合并
        List<Node<T>> merged = new ArrayList<>();
        int i = 0;
        while (i + 1 < nodes.size()) {
            merged.add(mergeRoots(nodes.get(i), nodes.get(i + 1)));
            i += 2;
        }
        // 如果奇数个，最后一个直接加入
        if (i < nodes.size()) {
            merged.add(nodes.get(i));
        }

        // 第二趟：从右到左依次合并
        Node<T> result = merged.get(merged.size() - 1);
        for (int j = merged.size() - 2; j >= 0; j--) {
            result = mergeRoots(result, merged.get(j));
        }

        return result;
    }

    /**
     * 减小键值（需要知道节点引用）
     * 时间复杂度：O(1) 均摊
     */
    public void decreaseKey(Node<T> node, T newKey) {
        if (newKey.compareTo(node.key) >= 0) {
            throw new IllegalArgumentException("New key must be smaller");
        }

        node.key = newKey;

        // 如果node是根节点，直接返回
        if (node == root) return;

        // 从父节点的子节点链表中移除node
        if (node.next == node) {
            // node是唯一的子节点
            node.parent.child = null;
        } else {
            // 从循环链表中移除
            node.prev.next = node.next;
            node.next.prev = node.prev;
            if (node.parent.child == node) {
                node.parent.child = node.next;
            }
        }

        node.parent = null;
        node.next = node;
        node.prev = node;

        // 将node作为新堆与root合并
        root = mergeRoots(root, node);
    }

    /**
     * 获取根节点引用（用于decreaseKey）
     */
    public Node<T> getRoot() {
        return root;
    }

    /**
     * 打印堆结构（调试用）
     */
    public void printHeap() {
        System.out.println("PairingHeap (size=" + size + "):");
        if (root != null) {
            printNode(root, 0);
        }
    }

    private void printNode(Node<T> node, int depth) {
        String indent = "  ".repeat(depth);
        System.out.println(indent + node.key);
        if (node.child != null) {
            Node<T> cur = node.child;
            do {
                printNode(cur, depth + 1);
                cur = cur.next;
            } while (cur != node.child);
        }
    }

    /**
     * 主函数：测试配对堆
     */
    public static void main(String[] args) {
        // 测试1：基本操作
        System.out.println("=== 测试1：基本插入与删除 ===");
        PairingHeap<Integer> heap = new PairingHeap<>();
        int[] values = {5, 3, 8, 1, 9, 2, 7, 4, 6};
        for (int v : values) {
            heap.insert(v);
            System.out.println("插入 " + v + "，当前最小值: " + heap.findMin());
        }

        System.out.println("\n堆结构:");
        heap.printHeap();

        System.out.println("\n依次删除最小值:");
        while (!heap.isEmpty()) {
            System.out.print(heap.deleteMin() + " ");
        }
        System.out.println();

        // 测试2：合并操作
        System.out.println("\n=== 测试2：堆合并 ===");
        PairingHeap<Integer> heap1 = new PairingHeap<>();
        PairingHeap<Integer> heap2 = new PairingHeap<>();
        for (int i = 1; i <= 5; i++) heap1.insert(i * 2);      // 2,4,6,8,10
        for (int i = 1; i <= 5; i++) heap2.insert(i * 2 - 1);  // 1,3,5,7,9

        System.out.println("堆1最小值: " + heap1.findMin());
        System.out.println("堆2最小值: " + heap2.findMin());

        heap1.merge(heap2);
        System.out.println("合并后最小值: " + heap1.findMin());
        System.out.println("合并后大小: " + heap1.size());

        // 测试3：与Java优先队列性能对比
        System.out.println("\n=== 测试3：性能对比（配对堆 vs PriorityQueue） ===");
        int n = 100000;
        Random rand = new Random(42);

        // PriorityQueue测试
        long start1 = System.currentTimeMillis();
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int i = 0; i < n; i++) pq.add(rand.nextInt(n));
        while (!pq.isEmpty()) pq.poll();
        long time1 = System.currentTimeMillis() - start1;

        // 配对堆测试
        rand = new Random(42);
        long start2 = System.currentTimeMillis();
        PairingHeap<Integer> ph = new PairingHeap<>();
        for (int i = 0; i < n; i++) ph.insert(rand.nextInt(n));
        while (!ph.isEmpty()) ph.deleteMin();
        long time2 = System.currentTimeMillis() - start2;

        System.out.println("PriorityQueue: " + time1 + " ms");
        System.out.println("PairingHeap: " + time2 + " ms");

        // 测试4：大量重复元素
        System.out.println("\n=== 测试4：大量重复元素 ===");
        PairingHeap<Integer> heap3 = new PairingHeap<>();
        for (int i = 0; i < 20; i++) heap3.insert(5);
        heap3.insert(1);
        heap3.insert(10);
        System.out.println("最小值: " + heap3.findMin());
        System.out.println("大小: " + heap3.size());
        while (!heap3.isEmpty()) {
            System.out.print(heap3.deleteMin() + " ");
        }
        System.out.println();
    }
}

摊还分析

配对堆的精确时间复杂度分析是一个长期未解决的开放问题。目前公认的结果如下：

为什么两趟合并法有效？

第一趟将 $k$ 个子节点两两合并，产生约 $k/2$ 棵新树。第二趟将这些树从右到左合并。

这种策略保证：最近插入/合并的节点优先参与合并，使得树结构保持相对平衡。与单次从左到右顺序合并相比，两趟合并法在摊还意义下将树高控制在 $O(\log n)$。

与斐波那契堆的对比

应用场景

1. Dijkstra最短路径：decreaseKey 优化使总复杂度从 $O(m \log n)$ 提升到 $O(m + n \log n)$
2. Prim最小生成树：同上
3. 任务调度：支持动态优先级调整和任务合并
4. 实时系统：简单实现降低bug风险和内存开销

扩展阅读

配对堆的变种包括：
– Splay堆：基于伸展树实现
– 斜堆（Skew Heap）：更简单的自调整堆
– Rank配对堆：引入秩信息优化合并策略
– 最优合并树：哈夫曼编码中的特殊应用