Sunday面试指南

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 也不支持未经同步的并发修改。

PriorityQueue 保证队头优先级,不保证 for-each 有序

知识点详解:有堆序,为什么还不算排好序?

先看一棵满足条件、却没有排成一列的树

假设小顶堆的底层数组是 [1, 4, 2, 8, 5, 3]。把它按照完全二叉树展开,1 的孩子是 4 和 2,4 的孩子是 8 和 5,2 的孩子是 3。

每个父节点都不大于孩子,因此它是合法的小顶堆。可是按照数组顺序遍历时,4 就出现在 2 前面,显然不是从小到大。

堆保留的是足以选出最小值的局部关系。它没有额外花成本把每个元素都排到全局位置。理解这一点,就不会把迭代器当成排序后的视图。PriorityQueue API明确说明了遍历顺序不受保证。

合法小顶堆的层序数组为 1、4、2、8、5、3,并非全局递增

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

浏览公司面试真题 →
简历汪永久免费在线制作简历,模板直接套用、导出无水印,永久免费、下载免费,不需要付费解锁任何功能。去写简历