每日算法 — 使用java实现二项堆：级联合并与度数约束维护

引言

二项堆（Binomial Heap）是一种优雅的高级数据结构，它由一组满足特定性质的二项树组成。与普通二叉堆相比，二项堆的最大优势在于支持 O(log n) 时间复杂度的堆合并操作，而二叉堆合并需要 O(n)。这一特性使二项堆在需要频繁合并堆的场景（如图算法中的优先队列）中表现优异。本文将用 Java 完整实现二项堆，并深入讲解其核心算法。

二项树的定义与性质

二项树 Bₖ 是一棵递归定义的有序树：
– B₀ 是只有一个节点的树
– Bₖ 由两棵 Bₖ₋₁ 连接而成，其中一棵的根成为另一棵根的最左孩子

关键性质：Bₖ 恰好有 2ᵏ 个节点，高度为 k，根节点的度数为 k。

二项堆的结构

二项堆 H 满足以下不变性：
1. H 中的每棵树都是二项树
2. 堆中任意节点的关键字不小于其父节点的关键字（最小堆性质）
3. 对于每个度数 k，堆中至多存在一棵二项树 Bₖ

这意味着含有 n 个节点的二项堆，其二项树的数量等于 n 的二进制表示中 1 的个数，最多为 ⌊log₂n⌋ + 1 棵。

核心操作：级联合并（Union）

合并两个二项堆的算法类似于二进制加法：
– 将两个堆的根表按度数升序排列
– 从左到右遍历，当遇到两棵度数相同的二项树时，合并它们（度数小的根作为子树）
– 若合并后仍与下一棵同度数，则继续向上合并（类似进位）

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

/**
 * 二项堆实现 —— 支持高效合并的最小堆
 * @param <T> 元素类型，需实现Comparable接口
 */
public class BinomialHeap<T extends Comparable<T>> {

    /**
     * 二项树节点
     */
    static class BinomialNode<T> {
        T key;                    // 节点关键字
        int degree;               // 节点度数（孩子数量）
        BinomialNode<T> parent;   // 父节点
        BinomialNode<T> child;    // 最左孩子
        BinomialNode<T> sibling;  // 右兄弟

        BinomialNode(T key) {
            this.key = key;
            this.degree = 0;
            this.parent = null;
            this.child = null;
            this.sibling = null;
        }
    }

    private BinomialNode<T> head;  // 根链表的头指针
    private int size;              // 堆中元素总数

    public BinomialHeap() {
        this.head = null;
        this.size = 0;
    }

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

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

    /**
     * 查找最小关键字节点
     * 时间复杂度: O(log n)
     */
    public T findMinimum() {
        if (isEmpty()) {
            throw new IllegalStateException("堆为空");
        }
        BinomialNode<T> minNode = head;
        BinomialNode<T> curr = head.sibling;
        // 遍历根链表，寻找最小关键字
        while (curr != null) {
            if (curr.key.compareTo(minNode.key) < 0) {
                minNode = curr;
            }
            curr = curr.sibling;
        }
        return minNode.key;
    }

    /**
     * 链接两棵度数相同的二项树
     * 使 y 成为 z 的孩子，要求 z.key <= y.key
     * 时间复杂度: O(1)
     */
    private void link(BinomialNode<T> y, BinomialNode<T> z) {
        y.parent = z;
        y.sibling = z.child;   // y 成为 z 的最左孩子
        z.child = y;
        z.degree++;            // z 的度数增加
    }

    /**
     * 合并两个二项堆的根链表（按度数升序）
     * 这是 union 操作的辅助步骤
     */
    private BinomialNode<T> mergeRoots(BinomialHeap<T> other) {
        if (this.head == null) return other.head;
        if (other.head == null) return this.head;

        // 使用归并排序的思想合并两个有序链表
        BinomialNode<T> dummy = new BinomialNode<>(null);
        BinomialNode<T> tail = dummy;
        BinomialNode<T> p1 = this.head;
        BinomialNode<T> p2 = other.head;

        while (p1 != null && p2 != null) {
            if (p1.degree <= p2.degree) {
                tail.sibling = p1;
                p1 = p1.sibling;
            } else {
                tail.sibling = p2;
                p2 = p2.sibling;
            }
            tail = tail.sibling;
        }
        tail.sibling = (p1 != null) ? p1 : p2;
        return dummy.sibling;
    }

    /**
     * 合并（Union）两个二项堆
     * 时间复杂度: O(log n)
     */
    public void union(BinomialHeap<T> other) {
        if (other == null || other.isEmpty()) {
            return;
        }
        // 合并根链表
        BinomialNode<T> newHead = mergeRoots(other);
        if (newHead == null) return;

        BinomialNode<T> prev = null;
        BinomialNode<T> curr = newHead;
        BinomialNode<T> next = curr.sibling;

        // 处理度数相同的树：类似二进制加法进位
        while (next != null) {
            // 情况1: 当前和下一棵度数不同，直接前进
            // 情况2: 下下棵也存在且度数相同，先处理后面的（延迟进位）
            if (curr.degree != next.degree ||
                (next.sibling != null && next.sibling.degree == curr.degree)) {
                prev = curr;
                curr = next;
            }
            // 情况3: 当前节点关键字较小，将 next 链接为 curr 的孩子
            else if (curr.key.compareTo(next.key) <= 0) {
                curr.sibling = next.sibling;
                link(next, curr);
            }
            // 情况4: next 节点关键字较小，将 curr 链接为 next 的孩子
            else {
                if (prev == null) {
                    newHead = next;
                } else {
                    prev.sibling = next;
                }
                link(curr, next);
                curr = next;
            }
            next = curr.sibling;
        }

        this.head = newHead;
        this.size += other.size;
        other.head = null;
        other.size = 0;
    }

    /**
     * 插入新元素
     * 将单元素堆与当前堆合并
     * 均摊时间复杂度: O(1)
     */
    public void insert(T key) {
        BinomialHeap<T> newHeap = new BinomialHeap<>();
        newHeap.head = new BinomialNode<>(key);
        newHeap.size = 1;
        union(newHeap);
    }

    /**
     * 提取（删除）最小元素
     * 时间复杂度: O(log n)
     */
    public T extractMin() {
        if (isEmpty()) {
            throw new IllegalStateException("堆为空");
        }

        // 1. 找到最小根节点
        BinomialNode<T> minNode = head;
        BinomialNode<T> minPrev = null;
        BinomialNode<T> curr = head;
        BinomialNode<T> prev = null;

        while (curr.sibling != null) {
            prev = curr;
            curr = curr.sibling;
            if (curr.key.compareTo(minNode.key) < 0) {
                minNode = curr;
                minPrev = prev;
            }
        }

        // 2. 将 minNode 从根链表中移除
        if (minPrev == null) {
            head = minNode.sibling;
        } else {
            minPrev.sibling = minNode.sibling;
        }

        // 3. 将 minNode 的孩子反转，形成新的二项堆
        BinomialHeap<T> childHeap = new BinomialHeap<>();
        BinomialNode<T> child = minNode.child;
        if (child != null) {
            // 反转孩子链表（兄弟指针原本从左到右，需要反转为根链表）
            List<BinomialNode<T>> children = new ArrayList<>();
            while (child != null) {
                child.parent = null;  // 切断与父节点的连接
                children.add(child);
                child = child.sibling;
            }
            Collections.reverse(children);
            childHeap.head = children.get(0);
            for (int i = 0; i < children.size() - 1; i++) {
                children.get(i).sibling = children.get(i + 1);
            }
            children.get(children.size() - 1).sibling = null;
            childHeap.size = (1 << minNode.degree) - 1;
        }

        // 4. 合并当前堆与子堆
        T minKey = minNode.key;
        union(childHeap);
        size--;
        return minKey;
    }

    /**
     * 减小指定节点的关键字值
     * 时间复杂度: O(log n)
     */
    public void decreaseKey(BinomialNode<T> node, T newKey) {
        if (newKey.compareTo(node.key) > 0) {
            throw new IllegalArgumentException("新关键字不能大于当前关键字");
        }
        node.key = newKey;
        // 向上冒泡，维护最小堆性质
        BinomialNode<T> curr = node;
        BinomialNode<T> parent = curr.parent;
        while (parent != null && curr.key.compareTo(parent.key) < 0) {
            // 交换关键字（实际应用中可能需要交换卫星数据）
            T temp = curr.key;
            curr.key = parent.key;
            parent.key = temp;
            curr = parent;
            parent = curr.parent;
        }
    }

    /**
     * 删除指定节点
     * 先 decreaseKey 到负无穷，再 extractMin
     * 时间复杂度: O(log n)
     */
    public void delete(BinomialNode<T> node) {
        // 将节点关键字设为最小可能值
        // 实际使用时需要确保类型支持极小值
        // 这里简化为先 decreaseKey 到比当前最小值还小的值
        decreaseKey(node, findMinimum());
        extractMin();
    }

    /**
     * 打印堆的结构（用于调试）
     */
    public void printHeap() {
        System.out.println("二项堆结构（共 " + size + " 个节点）:");
        BinomialNode<T> curr = head;
        while (curr != null) {
            System.out.print("B_" + curr.degree + ": ");
            printTree(curr, 0);
            curr = curr.sibling;
            System.out.println();
        }
    }

    private void printTree(BinomialNode<T> node, int depth) {
        if (node == null) return;
        System.out.print(node.key + " ");
        BinomialNode<T> child = node.child;
        while (child != null) {
            printTree(child, depth + 1);
            child = child.sibling;
        }
    }

    // ========== 测试入口 ==========
    public static void main(String[] args) {
        BinomialHeap<Integer> heap = new BinomialHeap<>();

        // 批量插入测试
        int[] values = {23, 7, 3, 17, 24, 18, 52, 38, 30, 26, 46, 39};
        System.out.println("插入元素: ");
        for (int v : values) {
            heap.insert(v);
            System.out.print(v + " ");
        }
        System.out.println("\n");

        System.out.println("最小值: " + heap.findMinimum());
        System.out.println("堆大小: " + heap.size());

        // 合并测试
        BinomialHeap<Integer> heap2 = new BinomialHeap<>();
        heap2.insert(1);
        heap2.insert(15);
        heap2.insert(42);
        System.out.println("\n合并前 heap2 最小值: " + heap2.findMinimum());
        heap.union(heap2);
        System.out.println("合并后最小值: " + heap.findMinimum());

        // 提取最小值测试
        System.out.println("\n按序提取最小值:");
        while (!heap.isEmpty()) {
            System.out.print(heap.extractMin() + " ");
        }
        System.out.println("\n提取完成，堆为空: " + heap.isEmpty());
    }
}

复杂度分析

与斐波那契堆的对比

二项堆是斐波那契堆的基础。斐波那契堆通过更宽松的树结构，将 decreaseKey 优化到 O(1) 均摊，但实现更复杂。在不需要频繁 decreaseKey 的场景下，二项堆因其简洁性和确定性复杂度仍是优选。

总结

二项堆通过二项树的级联结构，实现了堆的高效合并。其核心思想是将合并操作类比为二进制加法，度数相同的树逐级合并。掌握二项堆不仅能加深对堆数据结构的理解，也是学习更高级数据结构（如斐波那契堆）的重要基石。