Java PriorityQueue 底层是什么?为什么遍历结果不一定有序?
下面是一段用于讲解的模拟面试对话。
🧑💻 面试官: PriorityQueue 能让任务按优先级处理,对吧?
🙋♂️ 我: 对,优先级高的放在前面,遍历就能按顺序取出来。
🧑💻 面试官: 你说的是反复 poll,还是 for-each?
🙋♂️ 我: 它不是已经排好序了吗,这两个应该差不多。
🧑💻 面试官: 如果底层只保证父节点不大于子节点,左右子树又是谁先谁后?
PriorityQueue 保证的是“下一次应该取谁”,不是“任意遍历都已经有序”。
面试速答(60 秒版)
PriorityQueue 是 Java 基于优先级堆实现的队列。默认按照自然顺序,把最小元素放在队头;也可以提供 Comparator,定义自己的优先级。
堆只要求父节点不大于子节点,并不要求整个底层数组有序。所以 peek 能看到最小元素,连续 poll 能按优先级取出元素,但 iterator 和 for-each 都不保证有序。
常用操作中,offer、poll 的时间复杂度是 O(log n),peek 是 O(1)。按对象查找 contains,或者 remove(Object),通常需要线性扫描,不能因为它是队列就都当成 O(log n)。
同时,它不保证相同优先级按插入顺序出队。如果任务需要稳定顺序,要把序号也放进比较规则。普通 PriorityQueue 也不支持未经同步的并发修改。

知识点详解:有堆序,为什么还不算排好序?
先看一棵满足条件、却没有排成一列的树
假设小顶堆的底层数组是 [1, 4, 2, 8, 5, 3]。把它按照完全二叉树展开,1 的孩子是 4 和 2,4 的孩子是 8 和 5,2 的孩子是 3。
每个父节点都不大于孩子,因此它是合法的小顶堆。可是按照数组顺序遍历时,4 就出现在 2 前面,显然不是从小到大。
堆保留的是足以选出最小值的局部关系。它没有额外花成本把每个元素都排到全局位置。理解这一点,就不会把迭代器当成排序后的视图。PriorityQueue API明确说明了遍历顺序不受保证。

poll 之后,堆怎样继续工作?
取走根节点以后,需要把堆恢复成一棵完全二叉树。常见做法是把最后一个元素挪到根,再不断与更小的孩子比较,向下调整。
它不是把整个数组重新排序,而是在一条树路径上修复堆序。堆的高度与 log n 同阶,所以删除队头和插入新元素的调整成本通常是 O(log n)。插入时则把元素放到数组末端,再向上与父节点比较。OpenJDK 21 实现可以看到这些调整方法。
因此,如果只是想按优先级打印,又不想清空原队列,可以先复制一份队列,再反复 poll。直接把原队列拿来 poll,会把原来的任务一起消费掉。
相同优先级,还要不要保持先来后到?
假设有两个任务,优先级都为 3,一个先进入,一个后进入。如果比较器只比较优先级,它们比较结果就是 0。PriorityQueue 不会因此承诺先进先出。
如果业务需要先来后到,就让任务携带一个递增序号,先比较优先级,再比较序号。这样顺序来自明确的比较规则,而不是碰巧某次运行的堆布局。
比较数字时也不要直接返回 a.priority - b.priority,整数相减可能溢出,让大小关系反过来。使用 Integer.compare 或比较器组合更清楚。
任务入队以后,优先级可以直接改吗?
这是另一个容易漏掉的地方。队列不会持续监听对象内部字段。如果任务已经入队,外部直接把它的优先级从 9 改成 1,底层堆不会自动重新调整。
结果就是,按现在的字段看它应该先执行,实际位置却还在原处。可以根据设计先移除、更新、重新入队;如果存在并发,还要把这一组操作放进合适的同步边界。另一种做法是让队列元素不可变,通过新任务版本和失效标记管理更新。
PriorityQueue 也不接受 null。使用自定义比较器时,参与比较的元素需要满足比较契约。排序规则混乱,堆就不能替业务维持一个可靠的优先级。

怎样验证没有把 API 用错?
准备乱序输入,分别观察 for-each 和重复 poll 的结果,但不要断言 for-each 必然等于某个特定排列。它“不保证有序”,不代表每次都一定乱序。
再加上相同优先级任务,验证序号规则;测试最大、最小整数,防止减法溢出;最后检查对象入队后是否还会被其他代码修改。性能测试也要分开测队头操作与按对象删除,不能用一个数字概括所有操作。
面试官继续追问
PriorityQueue 是大顶堆还是小顶堆?
默认按自然顺序取最小值。换成逆序比较器,可以让最大元素优先。准确说,是比较器定义的“最小”元素在队头。
多线程共享,换成 PriorityBlockingQueue 就够了吗?
它提供并发访问和阻塞获取能力,但不自动解决任务背压、稳定排序、可变优先级等问题。尤其要核对容量语义,不能把名字里的 Blocking 当作有界接纳承诺。
为什么不直接用排序数组?
如果数据一次准备好、后面只顺序读取,排序很合适。如果不断插入新任务,又不断取当前最优者,堆能避免每次重新整体排序。看更新方式,而不只是看容器名字。
面试速记卡
- 堆序:父节点不大于孩子,不等于整个数组有序。
- 读取:peek 看队头;反复 poll 按优先级取;遍历不保证顺序。
- 成本:offer、poll 为 O(log n),peek 为 O(1),对象查找与删除需注意线性扫描。
- 同优先级:需要先来后到时,把序号写进比较器。
- 可变元素:入队后改排序字段,不会自动修复堆。
公司面试真题
真题根据求职者公开面经整理,题意经过概括,非逐字原话或公司官方题库;本文为 Sunday 的独立解析。
美团 · Java后端 · 秋招
是否了解 Java PriorityQueue,其底层实现原理是什么?(题意整理)
美团 秋招面经 一面 ↗
原帖编辑于 2024-08-06