堆：最小堆、最大堆与优先队列

我对“堆：最小堆、最大堆与优先队列”的理解经历过一个从会背到会用的过程。其中最明显的一点是：优先队列 API 用起来很顺手，但我一开始不理解为什么堆只保证堆顶有序，却能高效完成不断取极值的任务。后来每次看到结论，我都会追问它省掉了哪一步、又付出了什么代价，这也是这篇文章的主线。

堆是一棵满足特殊偏序关系的完全二叉树。最小堆保证父节点不大于孩子，根节点因此是全局最小值；最大堆相反。它不保证整棵树完全有序，只保证“最重要的元素”随时位于根部。

它从哪里来

J. W. J. Williams 在 1964 年提出堆排序时系统使用了二叉堆。堆随后成为优先队列的经典实现：它不追求所有元素完全有序，而是用较低维护成本保证最重要的元素始终能被快速取出。

为什么通常用数组保存

完全二叉树从上到下、从左到右填充，不需要为每个节点保存指针。若索引从 0 开始：

最小堆的树形结构、数组映射和上下浮过程图

图：完全二叉树可以紧凑映射到数组，父子下标直接计算

数组紧凑、缓存友好，父子位置又能直接计算，这是堆比普通节点树更适合实现优先队列的原因。

上浮与下沉

插入新元素时先放到数组末尾，再不断与父节点比较并上浮；删除堆顶时，把末尾元素移到根部，再与更合适的孩子交换并下沉。

public final class MinHeap {
    private final java.util.ArrayList<Integer> values = new java.util.ArrayList<>();

    public void add(int value) {
        values.add(value);
        int i = values.size() - 1;
        while (i > 0) {
            int p = (i - 1) / 2;
            if (values.get(p) <= values.get(i)) break;
            java.util.Collections.swap(values, p, i);
            i = p;
        }
    }

    public int poll() {
        if (values.isEmpty()) throw new java.util.NoSuchElementException();
        int result = values.get(0);
        int last = values.remove(values.size() - 1);
        if (!values.isEmpty()) {
            values.set(0, last);
            siftDown(0);
        }
        return result;
    }

    private void siftDown(int i) {
        while (true) {
            int left = i * 2 + 1;
            if (left >= values.size()) return;
            int right = left + 1;
            int smaller = right < values.size() && values.get(right) < values.get(left) ? right : left;
            if (values.get(i) <= values.get(smaller)) return;
            java.util.Collections.swap(values, i, smaller);
            i = smaller;
        }
    }
}

操作	复杂度
查看堆顶	`O(1)`
插入	`O(log n)`
删除堆顶	`O(log n)`
查找任意值	`O(n)`
批量建堆	`O(n)`

为什么批量建堆是 O(n)

把每个元素逐个插入堆需要 O(n log n)。更高效的方法是把数组视为完全二叉树，从最后一个非叶子节点开始向前执行下沉：

static void heapify(int[] values) {
    for (int i = values.length / 2 - 1; i >= 0; i--) {
        siftDown(values, i, values.length);
    }
}

虽然单次下沉最坏为 O(log n)，但绝大多数节点靠近叶子，可下沉高度很小，按所有节点高度求和后总成本为 O(n)。

堆排序

升序堆排序先建最大堆，把根部最大值与数组末尾交换，再缩小堆范围并下沉新根，重复直到结束。

时间复杂度稳定为 O(n log n)。
原地实现时额外空间为 O(1)。
通常不稳定，相等元素的相对顺序可能变化。
缓存访问和常数因素使它在通用内存排序中不一定优于优化后的快速排序。

堆排序展示了同一个不变量怎样支持不同目标：优先队列保留堆持续增删，堆排序则不断把极值放到最终位置。

优先队列不是有序列表

遍历 PriorityQueue 得到的顺序不保证从小到大；只有每次 poll 才能保证取出当前最小元素。需要完整排序时应使用排序算法，需要持续维护极值时才选择堆。

典型场景包括任务调度、Top K、合并多个有序流、Dijkstra 最短路径和延迟队列。Top K 若只保留最大的 K 个元素，可维护大小为 K 的最小堆，把空间从 O(n) 降到 O(k)。

static java.util.List<Integer> topK(int[] values, int k) {
    if (k <= 0) return java.util.List.of();
    java.util.PriorityQueue<Integer> heap = new java.util.PriorityQueue<>();
    for (int value : values) {
        if (heap.size() < k) heap.offer(value);
        else if (value > heap.peek()) {
            heap.poll();
            heap.offer(value);
        }
    }
    java.util.ArrayList<Integer> result = new java.util.ArrayList<>(heap);
    result.sort(java.util.Comparator.reverseOrder());
    return result;
}

当 k 远小于 n 时，总成本约为 O(n log k)，比完整排序更合适。

比较器与可变对象

PriorityQueue 的比较器必须具有稳定、一致的顺序关系。不要用 a - b 比较整数，差值可能溢出，应使用 Integer.compare(a, b)。对象入堆后修改参与比较的字段，堆不会自动感知，应删除后重新插入，或存入不可变快照。

如果需要支持“降低某节点优先级”，标准 PriorityQueue 没有高效定位元素的索引。Dijkstra 实现常采用重复插入新距离、出队时丢弃过期项，或自定义带位置索引的堆。

易错点

比较器与 equals 不一致并不一定非法，但会让“相等”语义难以理解。
修改已经入堆对象的排序字段，不会自动重新调整堆。
误以为堆支持任意元素的 O(log n) 查找。
下沉时没有选择两个孩子中更合适的一个。

测试清单

空堆和单元素堆。
递增、递减、全相等和随机数组。
每次操作后验证所有父节点满足堆序。
连续 poll 的结果是否有序。
批量 heapify 与逐个 add 得到的堆顶是否一致。
自定义比较器、极值整数和可变对象风险。