每日算法 — 使用java实现斜堆：可并堆与贪心合并策略

引言

斜堆（Skew Heap）是一种简洁而高效的可并堆（Mergeable Heap）数据结构，由Sleator和Tarjan于1986年提出。与左偏树、二项堆和斐波那契堆相比，斜堆无需维护额外的节点秩（rank）或度数信息，仅通过一种简单的”斜向合并”策略就能保证摊还时间复杂度为O(log n)。本文将用Java完整实现斜堆，讲解其无秩合并的核心思想，并展示如何在游戏开发中利用可并堆高效合并多个优先级队列。

算法核心思想

斜堆是一种满足堆性质（小根堆：父节点值不大于子节点值）的二叉树。其核心操作是合并（merge），其他所有操作（插入、删除最小值）都可由合并派生：

• 插入：将新节点视为单节点堆，与原堆合并。
• 删除最小值：合并根节点的左右子树。
• 合并两个堆：比较两堆根节点，将较小根作为新根，并将其右子树与另一堆递归合并，合并结果作为新根的左子树，原左子树变为右子树。

关键技巧在于交换左右子树：每次合并时，将递归合并的结果放在左子节点位置，而原来的左子树被”推到”右子节点。这种”斜向”交换避免了树深度单向增长，使摊还复杂度保持在对数级别。

Java实现

import java.util.*;

/**
 * 斜堆（Skew Heap）实现
 * 无秩可并堆，支持高效的堆合并操作
 */
public class SkewHeap<T extends Comparable<T>> {

    // 节点定义
    static class Node<T> {
        T value;           // 节点值
        Node<T> left;      // 左子节点
        Node<T> right;     // 右子节点

        public Node(T value) {
            this.value = value;
            this.left = null;
            this.right = null;
        }
    }

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

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

    /**
     * 合并两个斜堆
     * 核心操作：将较小根作为新根，右子树与另一堆合并，结果放左边，原左子树放右边
     */
    public void merge(SkewHeap<T> other) {
        if (other == null || other.root == null) return;
        this.root = mergeNodes(this.root, other.root);
        this.size += other.size;
        other.root = null;
        other.size = 0;
    }

    private Node<T> mergeNodes(Node<T> a, Node<T> b) {
        if (a == null) return b;
        if (b == null) return a;

        // 确保a的根值较小（小根堆）
        if (a.value.compareTo(b.value) > 0) {
            Node<T> temp = a;
            a = b;
            b = temp;
        }

        // 将a的右子树与b合并
        Node<T> mergedRight = mergeNodes(a.right, b);

        // 交换左右子树：合并结果放左边，原左子树放右边
        a.right = a.left;
        a.left = mergedRight;

        return a;
    }

    /**
     * 插入元素
     */
    public void insert(T value) {
        Node<T> newNode = new Node<>(value);
        this.root = mergeNodes(this.root, newNode);
        this.size++;
    }

    /**
     * 查看最小值（不删除）
     */
    public T peekMin() {
        if (root == null) throw new NoSuchElementException("堆为空");
        return root.value;
    }

    /**
     * 删除并返回最小值
     */
    public T extractMin() {
        if (root == null) throw new NoSuchElementException("堆为空");
        T minValue = root.value;
        // 合并左右子树成为新的堆
        this.root = mergeNodes(root.left, root.right);
        this.size--;
        return minValue;
    }

    public boolean isEmpty() {
        return root == null;
    }

    public int size() {
        return size;
    }

    /**
     * 中序遍历打印（调试用）
     */
    public void inorderPrint() {
        inorder(root);
        System.out.println();
    }

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

    /**
     * 获取堆的深度
     */
    public int depth() {
        return depth(root);
    }

    private int depth(Node<T> node) {
        if (node == null) return 0;
        return 1 + Math.max(depth(node.left), depth(node.right));
    }

    // ========== 游戏应用示例：多阵营单位优先级调度 ==========

    /**
     * 游戏单位类，用于演示斜堆在游戏中的应用
     */
    static class GameUnit implements Comparable<GameUnit> {
        String name;           // 单位名称
        int priority;          // 行动优先级（数值越小优先级越高）
        int speed;             // 速度属性
        String faction;        // 所属阵营

        public GameUnit(String name, int priority, int speed, String faction) {
            this.name = name;
            this.priority = priority;
            this.speed = speed;
            this.faction = faction;
        }

        @Override
        public int compareTo(GameUnit other) {
            // 先按优先级排序，再按速度排序
            if (this.priority != other.priority) {
                return Integer.compare(this.priority, other.priority);
            }
            return Integer.compare(other.speed, this.speed); // 速度大的优先
        }

        @Override
        public String toString() {
            return String.format("%s[%s](pri=%d,spd=%d)", name, faction, priority, speed);
        }
    }

    /**
     * 多阵营回合制战斗系统
     * 每个阵营有自己的行动队列（斜堆），战局变化时快速合并队列
     */
    static class BattleSystem {
        // 各阵营的行动队列
        Map<String, SkewHeap<GameUnit>> factionQueues;
        SkewHeap<GameUnit> globalQueue;  // 全局合并后的队列

        public BattleSystem() {
            factionQueues = new HashMap<>();
            globalQueue = new SkewHeap<>();
        }

        // 添加阵营
        public void addFaction(String faction) {
            factionQueues.putIfAbsent(faction, new SkewHeap<>());
        }

        // 向阵营添加单位
        public void addUnit(String faction, GameUnit unit) {
            factionQueues.get(faction).insert(unit);
        }

        // 合并所有阵营队列为全局行动顺序
        public void buildGlobalQueue() {
            globalQueue = new SkewHeap<>();
            for (SkewHeap<GameUnit> queue : factionQueues.values()) {
                globalQueue.merge(queue);
            }
        }

        // 下一回合：取出优先级最高的单位行动
        public GameUnit nextTurn() {
            if (globalQueue.isEmpty()) {
                // 如果全局队列为空，重新从各阵营合并
                buildGlobalQueue();
            }
            return globalQueue.extractMin();
        }

        // 两个阵营结盟：合并他们的行动队列
        public void allyFactions(String factionA, String factionB) {
            SkewHeap<GameUnit> qA = factionQueues.get(factionA);
            SkewHeap<GameUnit> qB = factionQueues.get(factionB);
            if (qA != null && qB != null) {
                qA.merge(qB);
                factionQueues.put(factionB, qA); // B现在指向A的队列
            }
        }
    }

    public static void main(String[] args) {
        System.out.println("=== 斜堆基础测试 ===");
        SkewHeap<Integer> heap = new SkewHeap<>();
        int[] values = {5, 3, 8, 1, 9, 2, 7, 4, 6};
        for (int v : values) {
            heap.insert(v);
        }
        System.out.println("堆大小: " + heap.size());
        System.out.println("堆深度: " + heap.depth());
        System.out.print("按优先级提取: ");
        while (!heap.isEmpty()) {
            System.out.print(heap.extractMin() + " ");
        }
        System.out.println();

        System.out.println("\n=== 堆合并测试 ===");
        SkewHeap<Integer> heapA = new SkewHeap<>();
        SkewHeap<Integer> heapB = new SkewHeap<>();
        for (int v : new int[]{1, 5, 9, 13}) heapA.insert(v);
        for (int v : new int[]{2, 4, 6, 8, 10}) heapB.insert(v);
        heapA.merge(heapB);
        System.out.print("合并后提取: ");
        while (!heapA.isEmpty()) {
            System.out.print(heapA.extractMin() + " ");
        }
        System.out.println();

        System.out.println("\n=== 游戏战斗系统演示 ===");
        BattleSystem battle = new BattleSystem();
        battle.addFaction("联盟");
        battle.addFaction("部落");
        battle.addFaction("中立");

        battle.addUnit("联盟", new GameUnit("骑士", 1, 50, "联盟"));
        battle.addUnit("联盟", new GameUnit("法师", 2, 30, "联盟"));
        battle.addUnit("部落", new GameUnit("战士", 1, 45, "部落"));
        battle.addUnit("部落", new GameUnit("萨满", 3, 25, "部落"));
        battle.addUnit("中立", new GameUnit("佣兵", 2, 40, "中立"));

        battle.buildGlobalQueue();
        System.out.println("战斗开始，行动顺序:");
        for (int i = 1; i <= 5; i++) {
            GameUnit unit = battle.nextTurn();
            System.out.println("  回合" + i + ": " + unit);
        }

        System.out.println("\n联盟与部落结盟，合并行动队列...");
        battle.allyFactions("联盟", "部落");
        battle.addUnit("联盟", new GameUnit("新兵", 1, 35, "联盟"));
        battle.addUnit("部落", new GameUnit("猎手", 2, 38, "部落"));
    }
}

复杂度分析

斜堆的优势在于实现极简：相比左偏树无需维护距离（dist/npl），相比斐波那契堆无需维护度数和标记位。虽然单次操作可能达到线性，但均摊分析证明n次连续操作的摊还复杂度为O(log n)。在需要频繁合并多个优先队列的场景（如游戏的多阵营回合调度、K路归并等），斜堆是非常理想的选择。

总结

斜堆通过巧妙的”合并时交换左右子树”策略，在不维护任何平衡信息的情况下实现了高效的可并堆。本文不仅实现了斜堆的核心操作，还展示了其在游戏多阵营优先级调度中的实际应用。理解斜堆的设计思想，有助于加深对摊还分析和自适应数据结构的理解。