Java PriorityQueue 源码解析：二叉堆、入队出队与 TopK 实战

写这篇东西的起因是我在梳理 Java 集合框架时发现很多人的认知停留在PriorityQueue 就是个会自动排序的队列但真被问到它底层是数组还是链表入队时元素怎么找到自己的位置为什么迭代器遍历出来的顺序不是有序的就卡壳了。这些问题恰恰是面试和实际编码中最容易暴露理解深度的点。我花了几个晚上把 JDK 源码里 PriorityQueue 相关的方法逐个读了一遍结合调试和实战场景做了验证这篇就把我的完整理解写出来。1. 队列底层不是有序数组而是一棵隐式二叉堆先说结论PriorityQueue 底层是一个 Object 数组但这个数组在逻辑上被看成一棵完全二叉树。我们平时说的优先级队列本质上是用数组实现的二叉堆Binary HeapJava 的这个实现属于小顶堆——堆顶元素永远是队列中优先级最高的那个也就是最小的元素。1.1 数组下标里的父子关系堆的性质决定了数组下标之间存在固定的换算关系。对于下标为i的元素父节点下标(i - 1) 1等价于(i - 1) / 2左子节点下标(i 1) 1右子节点下标(i 1) 2我用一个实际例子演示假设队列中有这些元素[3, 8, 5, 12, 9, 7]它们在数组里是连续存放的逻辑堆的结构是这样的3 下标0 / \ 8 5 下标1、2 / \ / 12 9 7 下标3、4、5这棵树保证父节点不大于它的子节点但兄弟节点之间、不同分支之间没有大小约束。比如8和5谁大谁小无所谓12和9也不需要跟5比较。这是理解 PriorityQueue 所有操作的基础——它只保证局部偏序不做全局排序。1.2 为什么用数组不用链表用链表实现二叉堆不是不行但数组有天然优势完全二叉树用数组存储不会浪费空间而且通过下标访问父子和兄弟节点是 O(1) 操作CPU 缓存命中率也远高于散落的链表节点。代价就是扩容时需要搬移数组但队列扩容的频率远低于元素入队的频率均摊成本完全可接受。这个设计带来的直接推论是PriorityQueue 不支持 null 元素因为compareTo或者Comparator.compare无法处理 null。这一点后面讲入队逻辑时还会再验证。2. 构造与扩容那些容易被忽略的边界条件2.1 初始容量的计算PriorityQueue 有多个构造方法最常用的两个public PriorityQueue() { this(DEFAULT_INITIAL_CAPACITY, null); } public PriorityQueue(int initialCapacity) { this(initialCapacity, null); }DEFAULT_INITIAL_CAPACITY是 11。值得注意的是如果你传入的initialCapacity小于 1会直接抛IllegalArgumentException。这里有个不为人注意的细节如果通过集合构造比如new PriorityQueue(collection)实际初始容量是Math.max(1, 集合大小)而不是简单地取集合的size()。2.2 grow 方法的扩容策略扩容逻辑在grow(int minCapacity)里private void grow(int minCapacity) { int oldCapacity queue.length; // Double size if small; else grow by 50% int newCapacity oldCapacity ((oldCapacity 64) ? (oldCapacity 2) : (oldCapacity 1)); // overflow-conscious code if (newCapacity - MAX_ARRAY_SIZE 0) newCapacity hugeCapacity(minCapacity); queue Arrays.copyOf(queue, newCapacity); }JDK 8 的扩容策略是如果旧容量小于 64扩容后容量是oldCapacity * 2 2如果大于等于 64扩容 50%。为什么是 64 这个阈值因为小数组扩容翻倍增长的摊销成本更低大数组按 50% 增长可以减少内存浪费。这个思路和ArrayList不一样ArrayList 是固定 1.5 倍PriorityQueue 对小容量更激进。扩容的本质是用Arrays.copyOf生成新数组并迁移元素这是一个 O(n) 操作但均摊到每次入队就是 O(1)。如果你能预估元素量最好在构造时就指定容量避免中途扩容。这里还有个溢出保护逻辑如果计算出的newCapacity超过MAX_ARRAY_SIZEInteger.MAX_VALUE - 8会调用hugeCapacity处理容量上限是Integer.MAX_VALUE。这个保护很重要因为数组长度在 JVM 里是带符号 int 的超过Integer.MAX_VALUE - 8就可能触发 OOM。3. 入队源码走读siftUp 上浮让新元素找到位置入队操作对外是offer(E e)内部核心是siftUp。我先把完整链路贴出来再逐行拆解。3.1 offer 方法整体逻辑public boolean offer(E e) { if (e null) throw new NullPointerException(); modCount; int i size; if (i queue.length) grow(i 1); size i 1; if (i 0) queue[0] e; else siftUp(i, e); return true; }几个关键动作依次是查空、记录结构性修改次数、扩容检查、放入元素或执行上浮。注意modCount这个细节它服务于 fail-fast 迭代器可以理解成一个版本号迭代期间队列结构被修改就会抛ConcurrentModificationException。如果你向一个空队列插入第一个元素不需要比较直接放在queue[0]即可。这也解释了为什么 PriorityQueue 的offer永远返回true——它不像ArrayBlockingQueue有容量限制除非 OOM否则不会拒绝元素。3.2 siftUp 为什么是上浮而不是下沉看核心方法private void siftUp(int k, E x) { if (comparator ! null) siftUpUsingComparator(k, x); else siftUpComparable(k, x); } SuppressWarnings(unchecked) private void siftUpComparable(int k, E x) { Comparable? super E key (Comparable? super E) x; while (k 0) { int parent (k - 1) 1; Object e queue[parent]; if (key.compareTo((E) e) 0) break; queue[k] e; k parent; } queue[k] key; }新元素追加到数组尾部时它的下标是k它可能比父节点小。上浮的过程就是不断拿新元素跟父节点比较如果新元素更小就把父节点下移到当前空位新元素继续往上走直到新元素不小于父节点或者已经走到堆顶。用生活化类比就像往一个已按身高排好的队伍里插入一个新队员他个子矮就要一路往前挤挤到前面比他高的人后面为止。3.3 构造器选择Comparable 还是 ComparatorPriorityQueue 支持两种比较方式无参构造要求元素实现Comparable走siftUpComparableComparator构造走siftUpUsingComparator逻辑完全一样只是比较动作从key.compareTo(e)变成comparator.compare(x, (E) e)我的经验是业务对象作为队列元素时优先用Comparator。理由很实际一个类通常只有一个自然的compareTo语义但不同业务场景对最小的定义不同——可能是最早过期时间、最低价格、最高评分。用Comparator可以做到一个对象多套排序维度还不用改类定义。顺带提醒一个常见误解PriorityQueue 的offer时间复杂度是 O(log n)不是 O(1)。虽然它尾插是 O(1)但上浮调整最坏要比较到根节点比较次数是树高log2(n)。4. 出队源码走读siftDown 下沉维持堆结构出队操作是poll()它跟入队对称但调整方向相反逻辑也更复杂一些。4.1 poll 方法的完整执行路径public E poll() { if (size 0) return null; int s --size; modCount; E result (E) queue[0]; E x (E) queue[s]; queue[s] null; if (s ! 0) siftDown(0, x); return result; }执行过程拆成四步队列为空直接返回null这也意味着 PriorityQueue 不能用poll()判空后再插入null记录堆顶元素作为返回值把数组最后一个元素取出来原来的位置置空把最后一个元素放到堆顶位置然后执行下沉调整为什么要拿最后一个元素去填补堆顶因为要保证完全二叉树的形状不被破坏。如果直接把中间的某个元素挪到堆顶树可能就不完全了数组中间也会出现空洞。4.2 siftDown 的具体过程private void siftDownComparable(int k, E x) { Comparable? super E key (Comparable? super E)x; int half size 1; // loop while a non-leaf while (k half) { int child (k 1) 1; // assume left child is least Object c queue[child]; int right child 1; if (right size ((Comparable? super E) c).compareTo((E) queue[right]) 0) c queue[child right]; if (key.compareTo((E) c) 0) break; queue[k] c; k child; } queue[k] key; }half size 1是一个很巧妙的边界只有下标小于 half 的节点才有子节点。比如 size 是 7half 是 3下标 0、1、2 有子节点下标 3、4、5、6 都是叶子节点。如果待调整位置已经到叶子层就不需要再比较了。下沉策略是两子取小先默认左子节点较小然后看右子节点是否存在且更小如果右子更小就切换接着拿待插入元素跟这个较小的子节点比较如果待插入元素更小说明它找到了合适位置直接停否则把较小的子节点上移自己继续往下走。这个两子取小很关键——小顶堆的父节点必须小于等于两个子节点所以只需要跟较小的子节点比。如果跟较大的子节点比即使比不过较大子节点也不能保证比小子节点小堆性质就乱了。4.3 peek 为什么是 O(1)peek()就更简单了public E peek() { return (size 0) ? null : (E) queue[0]; }直接返回数组首元素不做任何调整。这是堆设计的红利——最小元素永远在树根。但要注意peek在队列为空时返回null所以调用方要自己处理空队列场景。5. 批量建堆heapify 如何做到 O(n)如果你用一个无序集合去构造 PriorityQueue比如new PriorityQueue(existingList)JDK 不会逐个offer而是调用heapify方法直接原地建堆。5.1 从最后一个非叶子节点开始下沉heapify的代码非常短private void heapify() { for (int i (size 1) - 1; i 0; i--) siftDown(i, (E) queue[i]); }从最后一个非叶子节点开始依次向前对每个节点执行siftDown。为什么不是从头开始因为叶子节点不需要下沉从最后倒数第二层开始做能保证处理某个节点时它的左右子树已经是合法堆。这个算法在数据结构里叫Floyd 建堆法时间复杂度是 O(n) 而不是 O(n log n)。直觉理解是层数越低的节点需要下沉的距离越短大部分节点都集中在树的底部它们几乎不需要移动整体工作量近似线性的。如果你在代码里用循环 offer的方式初始化一个 n 个元素的队列复杂度是 O(n log n)而直接用集合构造复杂度 O(n)。数据量一大这个差距立刻体现出来。我在构造 100 万元素队列的测试里heapify 方式大概快了一个数量级。5.2 为什么面试题常问建堆为什么是 O(n)很多人不信这个复杂度因为siftDown看起来是 O(log n)外层循环 n/2 次怎么会是 O(n)关键在于绝大部分节点的下沉深度很小。做一个简单的数学估算堆里第 h 层的节点有2^h个但它们最多只需要下沉log2(n) - h层。把所有层的下沉工作量加起来是一个收敛的级数总和是 O(n)。这是理解堆性能分水岭的重要一关。建议你对比一下逐个上浮和统一下沉两种建堆方式的差异理解透了面试时就能讲得比别人深一层。6. remove(Object) 与迭代器PriorityQueue 的查找软肋与弱一致遍历PriorityQueue 在查找任意元素这件事上没有任何优化因为它不是为随机访问设计的。6.1 从任意位置移除元素的两个动作public boolean remove(Object o) { int i indexOf(o); if (i -1) return false; else { removeAt(i); return true; } }indexOf就是线性扫描数组时间复杂度 O(n)。真正有意思的是removeAtprivate E removeAt(int i) { modCount; int s --size; if (s i) // removed last element queue[i] null; else { E moved (E) queue[s]; queue[s] null; siftDown(i, moved); if (queue[i] moved) { siftUp(i, moved); if (queue[i] ! moved) return moved; } } return null; }这里有个非常巧妙的处理先用最后一个元素填补空缺执行siftDown如果下沉后元素没动过位置说明它比所有子节点都小但它可能比父节点还小这时需要反过来执行siftUp上浮。很多人在分析 remove 时只提下沉不提这个下沉失败后补一次上浮的分支——但实际场景里拿尾部元素补到中间位置时很可能遇到比子节点小但比父节点也小的情况缺了这步堆性质就坏了。6.2 迭代器的弱一致性体现在哪PriorityQueue 的迭代器是基于数组快照的不它不是快照而是直接遍历内部数组同时通过modCount做 fail-fast。但它有个特殊行为迭代器内部维护了一个forgetMeNot队列如果迭代过程中元素被remove()移除且不是尾部被移除的元素会被放进forgetMeNot后续迭代器会把它也遍历出来。这导致的直接后果是迭代器遍历顺序既不是堆序也不保证和元素插入顺序一致。比如我插入[5, 3, 9, 1]数组内容是[1, 3, 9, 5]迭代器遍历出来就是1, 3, 9, 5而不是排序后的1, 3, 5, 9。想要有序遍历正确姿势是循环poll()因为每次 poll 都取堆顶最小元素所以能按优先级顺序输出。但注意 poll 会清空队列如果需要保留原队列可以先用拷贝构造一个新队列再 poll。7. 从源码回到实战TopK 问题、合并有序列表与延迟队列场景7.1 用 PriorityQueue 解决 TopK 的固定套路求一个数据流里最大的 K 个元素用小顶堆堆顶就是当前第 K 大的元素新元素如果比堆顶大就替换堆顶并下沉。反过来求最小的 K 个元素用大顶堆通过Comparator.reverseOrder()。我贴一个实际用过的求 TopK 模板处理 10 亿级数据量时主要靠它做内存内预筛选public ListInteger topK(int[] nums, int k) { PriorityQueueInteger minHeap new PriorityQueue(k); for (int num : nums) { if (minHeap.size() k) { minHeap.offer(num); } else if (num minHeap.peek()) { minHeap.poll(); minHeap.offer(num); } } return new ArrayList(minHeap); }这样做的时间复杂度是 O(n log k)内存占用 O(k)。相比全局排序 O(n log n)当 n 远大于 k 时优势巨大。Java 8 之后也可以直接用自定义Collector但底层思路还是这个。7.2 合并 K 个有序链表LeetCode 23 题的经典解法就是 PriorityQueue 做多路归并把每个链表的头节点放进队列每次 poll 出最小节点然后把它的 next 节点补进队列循环直到队列为空。每个链表头节点入堆 O(k)每次 poll 和 offer 各 O(log k)总复杂度 O(n log k)。7.3 延迟队列的底层搭档Java 的DelayQueue内部就持有一个 PriorityQueue元素按getDelay(TimeUnit)返回值排序最早过期的任务在堆顶。这算是一个组合优于继承的好例子——延迟队列不需要重新实现排序逻辑只要定义好优先级规则就行。7.4 一个要注意的坑比较器不能与 equals 不一致PriorityQueue 的remove(Object)是通过indexOf线性查找的而indexOf用的是equals但堆序调整用的是Comparator。如果两个元素在比较器眼里相等但equals返回 false就会出现能入队但从堆结构上难以定位删除的现象。实际业务中我建议队列元素的比较器语义尽量和 equals 保持一致或者在需求层面明确相等即同一否则排查 bug 时会非常痛苦。再举个实际踩过的坑我用 PriorityQueue 做任务调度任务对象里有个timestamp字段用来排序但两个任务的timestamp相同时Comparator返回 0这时如果它们的equals因其他字段不同返回 falseremove(task)会找不到目标任务因为比较器只在堆内部调整时生效indexOf不看比较器。解决方案是给 Comparator 加一个次要排序键比如任务 ID确保比较结果和 equals 尽量一致。8. 性能边界与替代方案什么时候不该用 PriorityQueuePriorityQueue 不是万能的我整理了一份选型对照表方便你快速判断需求推荐结构原因频繁取最小/最大元素PriorityQueuepoll/offer 都是 O(log n)频繁随机访问或按下标修改ArrayList 手动排序数组按下标访问 O(1)需要严格的全局有序遍历TreeSet / 排序后的 ArrayList迭代就是有序的线程安全的优先级队列PriorityBlockingQueue内部加锁基于 PriorityQueue需要按插入顺序遍历LinkedList / ArrayDequeFIFO 语义清晰PriorityQueue 的并发能力是零它没有任何锁或 CAS 保护。多线程环境下要么自己加锁要么直接用PriorityBlockingQueue。PriorityBlockingQueue的源码就是在 PriorityQueue 外层套了ReentrantLock核心算法完全复用。另一个容易忽略的点是PriorityQueue 的自动扩容会搬移整个数组如果队列长期维持在大容量状态反复扩容会导致明显的 GC 压力和内存抖动。我在一个高频交易场景里就遇到过消息对象以每秒十万的速率进出队列默认容量 11 的队列几乎每次 offer 都在扩容后来直接预设容量 65536 才把性能稳下来。如果你需要大量吞吐又不想扩容可以考虑自己实现一个环形堆大根堆/小根堆都行或者用SizedPriorityQueue这类第三方实现。不过绝大多数业务场景JDK 自带版本已经足够了。最后再分享一个小技巧调试 PriorityQueue 时别只看toString()的输出因为它就是数组快照的样子不是树形结构。你可以写一个简单的递归打印方法把数组下标和元素值对应成树形图输出这样观察 siftUp/siftDown 的每一步变化会直观得多。我用这个方法给同事讲过一次堆调整过程比对着调试器看变量快十倍。