Java PriorityQueue：深入理解基于堆的实现原理

为什么学习 PriorityQueue？

PriorityQueue 是 Java 中最强大但也经常被误解的集合之一。

与 ArrayList 或 LinkedList 不同，它不仅仅是存储元素——它自动维护顺序，让你能够始终在 O(1) 时间内访问最小（或最大）元素。

这使它成为以下场景的首选：

任务调度 — 始终执行最高优先级的任务
图算法 — Dijkstra 最短路径、Prim 最小生成树
流处理 — 从数百万条记录中找出 Top K 元素
事件模拟 — 按时间顺序处理事件

但它是如何实现 O(log n) 的插入和删除的？答案就在其底层数据结构：二叉堆。

🎯 你将学到

主题	描述
堆基础	数组如何变成树
siftUp	插入如何维护堆性质
siftDown	删除如何维护堆性质
JDK 源码	实际实现细节
交互演示	逐步观察操作过程

📖 前置知识： 本文假设你已了解堆的基本概念。如果你是堆的新手，请先阅读我们的堆排序算法指南！

堆知识回顾

二叉堆是存储在数组中的完全二叉树。Java 的 PriorityQueue 默认使用最小堆，即：

父节点 ≤ 子节点（对所有节点成立）

数组到树的映射

对于索引 i 处的任意元素：

关系	公式
父节点	`(i - 1) / 2`
左子节点	`2 * i + 1`
右子节点	`2 * i + 2`

示例： 数组 [2, 4, 3, 7, 9, 5, 8] 表示为：

            [2]           ← 索引 0（根 = 最小值）
           /   \
         [4]   [3]        ← 索引 1, 2
        /  \   /  \
      [7] [9] [5] [8]     ← 索引 3, 4, 5, 6

最小值始终在索引 0。这就是为什么 peek() 是 O(1)！

JDK 源码结构

让我们深入 JDK 源码看看核心结构：

public class PriorityQueue<E> extends AbstractQueue<E> {
    
    // 堆数组 - 元素存储在这里
    transient Object[] queue;
    
    // 队列中的元素数量
    int size;
    
    // 可选的比较器，用于自定义排序
    private final Comparator<? super E> comparator;
    
    // 默认初始容量
    private static final int DEFAULT_INITIAL_CAPACITY = 11;
}

关键设计决策

使用 Object[] — Java 不能直接创建泛型数组，所以使用 Object[] 配合类型转换
默认容量是 11 — 一个看起来奇怪的数字，但提供了不错的初始空间
可选的比较器 — 如果为 null，元素必须实现 Comparable
动态扩容 — 数组满时自动增长

siftUp：插入的魔法

当你调用 offer(element) 时，新元素被添加到数组的末尾。但这可能会违反堆性质！

siftUp 通过将元素”向上冒泡”直到找到正确位置来修复这个问题。

算法

1. 将新元素放在末尾（index = size）
2. 与父节点比较：
   - 如果 元素 < 父节点 → 交换并重复
   - 如果 元素 ≥ 父节点 → 完成！

JDK 实现

可视化演示

让我们向堆 [2, 4, 3, 7, 9, 5, 8] 中插入 1：

步骤 1：添加到末尾
[2, 4, 3, 7, 9, 5, 8, 1]
                      ↑ 新元素

步骤 2：与父节点(7)比较
1 < 7 → 交换！
[2, 4, 3, 1, 9, 5, 8, 7]
          ↑

步骤 3：与父节点(4)比较
1 < 4 → 交换！
[2, 1, 3, 4, 9, 5, 8, 7]
    ↑

步骤 4：与父节点(2)比较
1 < 2 → 交换！
[1, 2, 3, 4, 9, 5, 8, 7]
 ↑ 新的根节点！

完成！新的最小值是 1。

为什么 siftUp 是正确的（证明）

这是关键问题：为什么 siftUp 之后结果仍然是一个有效的堆？

插入之前，我们有一个有效的最小堆，其中每个父节点 ≤ 其子节点。

将新元素放到末尾之后，只有一个地方可能违反堆性质：新元素与其父节点之间。

为什么？因为：

新元素位于叶子位置 — 它没有子节点
所有其他父子关系保持不变
唯一新增的关系是：新元素 ↔ 其父节点

siftUp 恰好修复这一个潜在的违规：

如果 新元素 >= 父节点 → 没有违规，完成！✅

如果 新元素 < 父节点 → 交换它们，然后检查祖父节点

每次交换后，为什么这一层的堆性质得到维护？

交换前（有效的最小堆）：     交换后：
    [P]                         [N]
   /   \                       /   \
 [N]   [S]        →         [P]   [S]

在原始堆中，P ≤ S（父节点 ≤ 兄弟节点，这是最小堆性质）。

交换后：

N ≤ P？ 是的 — 我们正是因为 N < P 才交换的
N ≤ S？ 是的 — 因为 N < P 且 P ≤ S，所以 N < P ≤ S ✓

这一层的堆性质恢复了！

那 P 的新位置呢？

P 移动到 N 原来的位置（最后一个位置，是叶子节点）。因为是叶子，P 没有子节点 — 不会有违规！

不变式： 我们只干扰从叶子到根的路径上的元素。兄弟子树完全未受影响。

💡 关键洞察： siftUp 就像向一个有序路径中插入。新元素”向上冒泡”直到找到它的排序位置，同时把更大的元素沿路径向下推。

为什么 siftUp 高效

最大比较次数： log₂(n) — 树的高度
无额外空间： 原地操作
提前终止： 一旦堆性质满足就停止

siftDown：删除的魔法

当你调用 poll() 时，根节点（最小值）被移除。但我们需要填补空缺！

siftDown 通过以下步骤处理：

将最后一个元素移到根
将它”下沉”直到堆性质恢复

算法

1. 保存根值（用于返回）
2. 将最后一个元素移到根
3. 与子节点比较：
   - 找到较小的子节点
   - 如果 元素 > 较小子节点 → 交换并重复
   - 如果 元素 ≤ 两个子节点 → 完成！

JDK 实现

可视化演示

让我们从堆 [2, 4, 3, 7, 9, 5, 8] 中 poll：

步骤 1：移除根，将最后一个移到根
[8, 4, 3, 7, 9, 5]  (返回 2)
 ↑ 新根

步骤 2：与子节点(4, 3)比较
较小子节点 = 3
8 > 3 → 交换！
[3, 4, 8, 7, 9, 5]
       ↑

步骤 3：与子节点(5)比较
8 > 5 → 交换！
[3, 4, 5, 7, 9, 8]
             ↑

步骤 4：没有更多子节点
完成！8 现在是叶子节点。

为什么 siftDown 是正确的（证明）

与 siftUp 一样，让我们回答关键问题：为什么 siftDown 之后结果仍然是一个有效的堆？

poll() 之后，我们：

移除根节点（最小值）
将最后一个元素移到根位置

哪里可能违反堆性质？

两个子树（根的左右子节点）仍然是有效的堆 — 我们只动了根，没有动它们！

将最后一个元素移到根之后：
        [L]  ← 最后一个元素（可能很大！）
       /   \
     [4]   [3]  ← 仍然是有效的堆
     / \   / \
    ...   ...

唯一可能的违规是：新根可能 > 其子节点。

siftDown 通过将元素向下沉来修复这个违规：

如果 元素 <= 较小子节点 → 没有违规，完成！✅

如果 元素 > 较小子节点 → 与较小子节点交换，重复

为什么要与较小的子节点交换？

这很关键！考虑：

       [8]         与哪个子节点交换？
      /   \
    [4]   [3]      较小的 = 3

如果与较大的子节点（4）交换：

       [4]         ❌ 错误！
      /   \
    [8]   [3]      现在 4 > 3，堆性质违规！

如果与较小的子节点（3）交换：

       [3]         ✅ 正确！
      /   \
    [4]   [8]      3 < 4，堆性质保持！

较小的子节点保证 ≤ 其兄弟节点，所以提升它可以维护这一层的堆性质。

交换后，为什么我们只需要继续向下？

       [3]          ← 这一层现在有效
      /   \
    [4]   [8]       ← 8 可能与它的子节点违规
          / \
        [5] [9]     ← 但这个子树未被触及

当前位置上方的路径已修复
兄弟子树（左侧）从未被触及
我们只需要从放置元素的位置向下修复路径

💡 关键洞察： siftDown 是 siftUp 的镜像。不是将可能太小的元素向上冒泡，而是将可能太大的元素向下沉。

优化：找到较小子节点

JDK 使用了一个巧妙的检查：

if (right < n && c.compareTo(es[right]) > 0)
    c = es[child = right];

这在一次比较中找到较小子节点，避免了分别比较两个子节点与父节点的需要。

交互式可视化

实际观察 siftUp 和 siftDown！使用控制按钮来：

offer() — 添加新元素并观察它向上冒泡
poll() — 移除最小值并观察替换元素下沉

Java PriorityQueue - 上浮与下沉演示

可视化 offer() 和 poll() 操作的内部工作原理

速度:

步骤 1/1

初始化

就绪。使用 offer() 添加元素或 poll() 移除最小元素。

堆树结构

堆数组 (queue)

[0]

[1]

[2]

[3]

[4]

[5]

[6]

根节点 (最小值)

上浮中

下沉中

交换中

新元素

尝试这些实验：

连续 offer 几个小数字（1, 2, 3）并观察它们争夺根位置
反复 poll 并观察堆如何重构
offer 一个很大的数字，注意它留在底部附近

offer() 和 poll() 操作

现在让我们看看完整的 offer() 和 poll() 实现：

操作总结

方法	描述	时间复杂度
`offer(e)`	添加元素，上浮	O(log n)
`poll()`	移除最小值，下沉	O(log n)
`peek()`	返回最小值但不移除	O(1)
`size()`	返回元素数量	O(1)
`contains(e)`	检查元素是否存在	O(n)
`remove(e)`	移除指定元素	O(n)

⚠️ 注意： contains() 和 remove(Object) 是 O(n) 因为它们需要扫描整个堆。请谨慎使用！

动态数组扩容

当内部数组满时，PriorityQueue 会自动扩容：

private void grow(int minCapacity) {
    int oldCapacity = queue.length;
    // 小容量时翻倍，大容量时增加 50%
    int newCapacity = oldCapacity + (
        (oldCapacity < 64) 
            ? (oldCapacity + 2) 
            : (oldCapacity >> 1)
    );
    // 检查溢出
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    queue = Arrays.copyOf(queue, newCapacity);
}

增长策略

当前大小	增长率
< 64	翻倍 + 2
≥ 64	增加 50%

这平衡了小队列的内存效率和大队列的性能。

时间复杂度分析

为什么是 O(log n)？

siftUp 和 siftDown 最多遍历从根到叶（或反向）的一条路径。

在有 n 个节点的完全二叉树中：

高度 = ⌊log₂(n)⌋
最大操作数 = 高度

offer() 的均摊分析

操作	最坏情况	均摊
数组访问	O(1)	O(1)
上浮	O(log n)	O(log n)
数组扩容	O(n)	O(1)*

*数组扩容很少发生，分摊到多次插入上。

与其他数据结构的比较

操作	PriorityQueue	有序数组	有序链表
插入	O(log n)	O(n)	O(n)
查找最小值	O(1)	O(1)	O(1)
移除最小值	O(log n)	O(n)	O(1)
从 n 个元素构建	O(n)	O(n log n)	O(n log n)

堆在大多数优先队列用例中都是赢家！

常见陷阱

1. 不允许 Null 元素

PriorityQueue<String> pq = new PriorityQueue<>();
pq.offer(null);  // ❌ NullPointerException!

2. 迭代器顺序 ≠ 优先级顺序

PriorityQueue<Integer> pq = new PriorityQueue<>(Arrays.asList(5, 1, 3));

// ❌ 错误：迭代器不按优先级顺序给出！
for (Integer i : pq) {
    System.out.println(i);  // 可能打印：1, 5, 3
}

// ✅ 正确：使用 poll() 获取优先级顺序
while (!pq.isEmpty()) {
    System.out.println(pq.poll());  // 打印：1, 3, 5
}

3. 插入后修改元素

class Task {
    int priority;
    // ...
}

PriorityQueue<Task> pq = new PriorityQueue<>(
    Comparator.comparing(t -> t.priority)
);

Task task = new Task(5);
pq.offer(task);

task.priority = 1;  // ❌ 堆不知道这个改变！
// pq.poll() 可能不会首先返回这个任务

解决方案： 移除、修改、重新插入：

pq.remove(task);
task.priority = 1;
pq.offer(task);

4. 最大堆的困惑

默认情况下，PriorityQueue 是最小堆。要使用最大堆：

// 方法 1：反向比较器
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(
    Collections.reverseOrder()
);

// 方法 2：自定义比较器
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(
    (a, b) -> b - a
);

延伸阅读

📚 深入学习堆知识

文章	描述
堆排序算法指南	学习 MAX-HEAPIFY、BUILD-MAX-HEAP 和完整的堆排序，配有交互式可视化

在堆排序文章中，你将发现：

为什么 BUILD-MAX-HEAP 是 O(n) 而不是 O(n log n)
MAX-HEAPIFY 与 siftDown 的区别
练习题：第 K 大元素、合并 K 个有序链表

核心要点

核心概念

概念	要点
数据结构	数组中的二叉最小堆
siftUp	插入后将新元素向上冒泡
siftDown	移除后将替换元素向下沉
索引公式	parent=(k-1)/2, left=2k+1, right=2k+2

性能

操作	复杂度
offer() / poll()	O(log n)
peek()	O(1)
contains() / remove(Object)	O(n)

最佳实践

✅ 用于基于优先级的处理
✅ 优先使用 poll() 而不是迭代来获取优先级顺序
✅ 对复杂排序使用自定义 Comparator
❌ 不要在插入后修改元素
❌ 不要期望迭代器给出优先级顺序

💡 总结： PriorityQueue 通过优雅的堆算法实现 O(log n) 操作。理解 siftUp 和 siftDown 不仅能让你掌握这个数据结构，还能打开整个堆相关算法家族的大门。