1. 先弄明白它的设计骨架为什么是数组为什么能保证O(logn)被问到“PriorityQueue底层是什么”时大多数人都能回答出“二叉堆”这三个字。但再追问一句“数组下标和二叉堆节点是怎么对应上的”不少背八股文的朋友就开始卡壳了。这很正常因为PriorityQueue的源码实现里堆从来不是像教科书那样从下标1开始的也没有单独的“节点”对象它就是把一棵完全二叉树直接拍扁到一个Object数组里。1.1 类声明与核心字段先看类结构。PriorityQueue继承自AbstractQueue实现了Serializable字段就五个public class PriorityQueueE extends AbstractQueueE implements java.io.Serializable { private static final int DEFAULT_INITIAL_CAPACITY 11; transient Object[] queue; // 底层数组 private int size 0; // 当前元素个数 private final Comparator? super E comparator; // 比较器可为null transient int modCount; // 结构性修改计数 }这里有几个容易被忽略的信息。queue数组注释明确要求“非空”这个约束很关键。size和queue.length不是一回事queue.length是容量size是实际元素个数。comparator是final的一旦构造确定就不能换了。modCount在Java集合框架里是老熟人PriorityQueue同样用它做fail-fast迭代器保护。重点说说comparator为null的情况。当构造器没有传比较器时PriorityQueue要求元素自身实现Comparable接口入队和出队时会强转成Comparable再比较。如果元素没有实现Comparable运行时抛ClassCastException而不是编译期报错。这个“延迟到运行时才发现”的特性是很多线上问题埋在深处的根源。1.2 数组下标就是一棵完全二叉树PriorityQueue用的是二叉最小堆堆顶永远是优先级最高值最小按comparator规则的元素。它和ArrayList一样用动态数组存数据区别在于数组下标被赋予了“父子关系”下标k的节点的父节点下标(k - 1) 1下标k的节点的左孩子下标(k 1) 1下标k的节点的右孩子下标(k 1) 2很多教材讲堆排序时习惯从下标1开始父节点用k/2这样虽然数学上漂亮但等于浪费了下标0。JDK选择了从0开始的方案省一个数组位还通过位运算替代乘除法性能更优。这个选择也决定了源码里到处是这种看起来有点费解的位移表达式。堆序性质体现在任意父节点都比它的两个子节点“小”。注意这个性质只约束父子之间不约束兄弟节点之间也不保证数组是全局有序的。也就是说你平铺这个数组它不是排好序的但每次弹出堆顶之后能保证剩下部分继续满足堆序。这也是“堆排序”和“普通排序”的核心差异堆维持的是局部有序的偏序关系而不是全序。1.3 默认容量11和比较器的两条分支为什么默认容量是11而不是16这个没查到官方特别权威的说法但可以合理推测JDK作者在写这个类时对“常见业务里队列初始元素数”做了个保守估计11不算大不会太浪费也足够覆盖大部分小规模场景。不过真在代码里用如果明确知道要装多少个元素还是建议显式指定初始容量避免频繁扩容。比较器存在两种模式源码里几乎所有调整方法都成对出现siftUpComparable / siftDownComparable走自然顺序元素必须实现ComparablesiftUpUsingComparator / siftDownUsingComparator走外部Comparator它们在操作上完全等价只是一个用强转后的Comparable自比较一个用comparator字段比较。看源码的时候记着这个规律两个方法读一个就够了另一个套路完全一样。2. 构造器从集合初始化时是怎么瞬间变成堆的很多人在PriorityQueue初始化上栽过跟头。new PriorityQueue(list)之后你以为元素已经排好序了并没有它只是完成了建堆数组看起来仍然“乱糟糟”的。要理解这个得看构造器内部到底走了什么逻辑。2.1 五类构造器入口PriorityQueue提供了多个构造器常见的有这些PriorityQueue() // 默认容量11自然顺序 PriorityQueue(int initialCapacity) // 指定容量自然顺序 PriorityQueue(int initialCapacity, Comparator? super E comparator) PriorityQueue(Collection? extends E c) // 从集合初始化 PriorityQueue(PriorityQueue? extends E c) // 从优先队列拷贝 PriorityQueue(SortedSet? extends E c) // 从有序集合初始化构造器里有个很微妙的分类逻辑当传入的是PriorityQueue或SortedSet时直接走initFromPriorityQueue或initFromSortedSet。因为这两种集合内部元素本身已经满足堆序SortedSet是按升序遍历直接按迭代顺序复制到数组即可无需重建堆。但传入的是普通Collection时就只能先复制出数组再调用heapify来建堆。这个设计体现了JDK对“已知有序来源”的信任和利用能省则省不能省才做重活。2.2 heapifyO(n)建堆而不是O(n log n)heapify是建堆的核心源码很短private void heapify() { for (int i (size 1) - 1; i 0; i--) siftDown(i, (E) queue[i]); }(size 1) - 1算出的是最后一个非叶子节点的下标。比如size10最后一个非叶子节点是下标4。循环从它开始往前逐个执行siftDown下沉直到根节点0。这个方向很讲究只有从下往上调整才能保证处理到某个节点时它的左右子树已经是合法堆这时只需要把当前节点下沉到正确位置即可。很多初学者会想当然地用“逐个offer建堆”那是O(n log n)的复杂度。heapify的妙处在于叶子节点不需要处理越靠近根部的节点数量越少虽然单个节点下沉代价高但总代价被“低频高价”和“高频低价”拉平数学上可以证明整体是O(n)。这是堆排序里最容易被低估的优化点面试时能主动讲出“批量建堆是线性复杂度”会显得你确实读过源码。2.3 从集合转数组的隐藏细节initFromCollection里有个检查容易被忽略private void initFromCollection(Collection? extends E c) { Object[] es c.toArray(); if (es.getClass() ! Object[].class) es Arrays.copyOf(es, es.length, Object[].class); queue es; size es.length; heapify(); }如果传入集合的toArray返回的不是Object[]类型比如TreeSet的toArray可能返回实际类型数组必须用Arrays.copyOf转成Object[]。这一步是为了后续put到queue数组时类型安全。很多自研框架的源码里都有这类防御性拷贝看多了你会发现Java集合类在“类型擦除时代”遗留下来的细节特别多。3. 入队的完整链路siftUp上浮加grow动态扩容“堆排序与动态调整的完美结合”这句话最直观的体现就是在offer方法里。offer承载了两件事把新元素放在堆尾并上浮到正确位置如果数组不够用先扩容再把元素放进去。顺序是先扩容后入堆而不是先塞进去再扩容这个顺序要记清楚。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; }第一步拒绝null。PriorityQueue底层依赖元素比较null没法参与任何比较所以直接抛NPE。第二步modCount。只要发生结构性修改插入、删除、清空这个计数就会变化迭代器靠它实现fail-fast。第三步判断是否需要扩容。这里有个反直觉的点size是当前元素个数它和数组长度相等时新元素下标就是size所以需要grow(size 1)。grow的参数是“所需最小容量”不是“要扩到多大”。第四步是精髓。如果队列原本为空新元素直接放queue[0]当堆顶不需要任何调整如果非空先放在数组末尾下标i处然后调用siftUp(i, e)让它一路向上找家。3.2 siftUp上浮的细节siftUp用“插入排序”的思路维护堆序新元素先坐在数组末尾然后反复和父节点比较如果比父节点小就把父节点往下挪自己继续往上试探直到找到合适位置。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; }注意break条件key.compareTo(parent) 0就停。意思是新元素只要不比父节点小就原地定居。这个条件保证了最小堆性质但同样值时新元素停在较深位置这直接导致了PriorityQueue的不稳定性。后面第5节我会专门演示这个现象。整个上浮过程最坏情况是从叶子一路换到根代价O(log n)。但由于新元素通常随机分布实际平均调整次数远小于树高这也是为什么PriorityQueue在动态数据流场景下比“每次维护一个有序数组”高效得多的根本原因。3.3 grow扩容的数学规则grow是“动态调整”的另一个主角。源码private void grow(int minCapacity) { int oldCapacity queue.length; int newCapacity oldCapacity ((oldCapacity 64) ? (oldCapacity 2) : (oldCapacity 1)); if (newCapacity MAX_ARRAY_SIZE) { newCapacity hugeCapacity(minCapacity); } queue Arrays.copyOf(queue, newCapacity); }这个扩容公式非常有意思。oldCapacity小于64时新容量是 oldCapacity * 2 2。大于等于64时新容量是 oldCapacity oldCapacity / 2也就是1.5倍。我们以默认容量11为例演算一下容量变化11 - 11 * 2 2 2424 - 24 * 2 2 5050 - 50 * 2 2 102102 - 102 51 153153 - 153 76 229看到没前三次接近翻倍之后就变成1.5倍。这个策略和ArrayList类似容量较小时快速翻倍减少扩容次数容量较大时控制增速避免一次性分配过大内存。grow期间要做Arrays.copyOf这是O(n)的数组拷贝但扩容量是倍增的均摊到每次offer上的成本其实很低。还需要提一下MAX_ARRAY_SIZE Integer.MAX_VALUE - 8。源码注释说得很清楚某些虚拟机在数组头部会存一些元信息数组实际最大长度可能比Integer.MAX_VALUE小强行分配太大会直接OutOfMemoryError。hugeCapacity就是兜底逻辑如果minCapacity溢出成负数直接抛OOM否则在MAX_ARRAY_SIZE和Integer.MAX_VALUE之间选择。3.4 扩容和堆调整的配合顺序很多人会觉得“扩容之后数组变了原来的堆结构是不是要重建”。完全不需要。因为堆结构完全靠数组下标之间的父子关系表达元素值不变、下标不变堆序就天然维持。扩容只是把数组复制到一块更大的连续内存上堆的性质不受任何影响。这也是“数组式堆”相比“链式堆”的优势之一扩容成本可控且不会破坏既有堆序。实际操作中我习惯在创建PriorityQueue时如果大概能预估数据量就把初始容量设得稍微宽裕一点。因为扩容终究是一次整数组拷贝数据量大时也会有毫秒级的停顿虽然不如HashMap扩容那么伤但能避免还是尽量避免。4. 出队和删除poll、removeAt与siftDown下沉入队看上浮出队看下沉。如果把PriorityQueue比作一个不断有新人插队的队伍那么出队就是“队长走了后面的人依次往前补位”的过程。但这里有个非常反直觉的设计补位的人不是左孩子或右孩子中的较小者而是数组末尾的最后一个元素。这背后的原因值得深挖。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; }流程分四步把堆顶result保存下来准备返回把数组最后一个元素x取出来将数组末尾置null帮助GC把x放到堆顶位置执行siftDown。为什么不直接让左、右孩子中的较小者当新堆顶因为如果直接把某个孩子提上来这个孩子原来的位置就空出来了还得从它的孩子里再选一个补位一路递归下去实现复杂且容易破坏结构。而把末尾元素提到堆顶虽然它大概率是个较大的值但通过一次下沉操作就能把它压到正确位置只需维护一条从根向下的路径代码干净很多。这也解释了为什么poll是O(log n)本质上是删除根节点后从根开始沿一条路径做下沉路径长度就是树高。peek和poll的区别也提醒一下peek只读queue[0]不修改结构时间复杂度O(1)也不会动modCount。4.2 siftDown下沉的边界判断siftDown的代码比siftUp复杂因为它有两个孩子要比较private void siftDownComparable(int k, E x) { Comparable? super E key (Comparable? super E) x; int half size 1; while (k half) { int child (k 1) 1; 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的节点没有孩子是叶子下沉没必要继续。每轮循环先找左孩子child如果右孩子存在且比左孩子更小就选右孩子为候选c。这一步非常关键下沉时要和孩子中较小者比较否则可能出现“父节点比右孩子大但比左孩子小”的情况导致堆序被破坏。找到较小孩子后如果key不比它大说明当前位置合适break否则把较小的孩子往上挪自己则进入孩子的位置继续下沉。整个过程像气泡往下沉越沉越深直到遇到一个“周围都比我小”的安稳位置。siftDown在堆排序里还承担着另一个使命。堆排序的经典步骤就是“交换堆顶和末尾元素缩小堆长度再从根下沉”PriorityQueue每次poll之后虽然没有交换元素到数组末尾但“从根下沉”的思想和堆排序是完全一致的。可以说PriorityQueue就是“永远只执行堆排序第一步”的数据结构。4.3 removeAt中那个精妙的上浮回退remove(Object o)会先线性扫描找到元素下标再调用removeAt(i)删掉。removeAt的设计比poll复杂得多因为它删除的不一定是堆顶可能是树中间任意位置的节点。private E removeAt(int i) { modCount; int s --size; if (s i) 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; }这段代码最有意思的是先用末尾元素moved填到被删位置i执行siftDown下沉。如果下沉结束后queue[i]还是moved说明moved在整棵子树里已经是最小了。但注意siftDown只关心子树它对“moved是否比父节点小”一无所知。moved是从数组末尾来的它可能非常小小到比父节点还小这时它应该继续“上浮”才对于是源码补了一次siftUp(i, moved)。这个“先下沉如果原地下沉不了再上浮”的双向调整保证了任意位置删除后堆序依然成立。网上不少源码分析文章只讲poll不讲removeAt其实面试里真正的加分点恰恰在这个回退逻辑上。把它讲清楚面试官会觉得你是真的啃过源码。另外注意removeAt的返回值。moved最终停在原地则返回null表示从迭代器视角来看没有元素被“移动到当前迭代位置之前”如果moved上浮到了更靠前的位置返回moved迭代器需要把它记录下来避免漏遍历。这个细节在实现迭代器删除时特别关键。5. 排序稳定性、并发安全与适用场景源码读完了接下来聊点工程层面的问题。PriorityQueue不是银弹它有明确的适用边界也有一个很容易被忽略的排序稳定性问题。5.1 为什么PriorityQueue不是稳定排序先做个实验。定义元素class Item { int value; String name; Item(int value, String name) { this.value value; this.name name; } }按顺序依次入队(1,a)、(2,b)、(1,c)、(0,d)然后依次poll。根据堆调整的路径最终得到的出队顺序很可能是(0,d)、(1,c)、(1,a)、(2,b)。看到问题没有value同为1的两个元素先入队的a反而排到了c后面。原因就在siftUp的break条件key.compareTo(parent) 0就停同值的新元素不会继续上浮穿越旧元素但旧元素可能在后续删除时被末尾元素顶掉位置导致相对顺序被打乱。堆排序本身就是不稳定的排序算法PriorityQueue在Javadoc里也明确写了“对于相等优先级元素不保证FIFO顺序”。如果业务上要求同优先级按入队先后出队必须自定义Comparator把入队序号作为次级排序键。5.2 和TreeMap、Arrays.sort的对比我在项目里见过不少同事在需要“每次取最小值”的场景里直接用了TreeMap或每次排序的ArrayList性能和代码可读性都打了折扣。做个简单对比维度PriorityQueueTreeMap/TreeSet每次Arrays.sort底层结构动态数组 二叉堆红黑树快排/TimSort插入复杂度O(log n)O(log n)每次O(n log n)取最小值O(1) peekO(log n) 拿first排序后O(1)遍历顺序数组顺序不保证有序按键有序完全有序重复元素允许TreeSet去重允许稳定性不稳定不适用/稳定需讨论对象排序稳定PriorityQueue最适合的场景是“动态数据流 只关心极值”。比如无止境地往系统里塞任务每次要优先处理最紧急的一个这种场景它几乎是理想选择。但如果你需要遍历所有元素时都有序那就别用PriorityQueue直接TreeMap或者排序后的ArrayList更合适。5.3 经典场景TopK、定时器、DijkstraPriorityQueue的真实应用遍地都是。最经典的是TopK问题在一个很大的数据流里维护最大的100个数做法就是建一个容量100的最小堆每个新元素如果比堆顶大就poll掉堆顶再offer新元素。这样堆里永远保存着当前最大的100个堆顶就是这100个里最小的那个。ScheduledThreadPoolExecutor内部也有一个基于堆的延迟队列叫DelayedWorkQueue它的结构核心就是优先队列思想只是额外增加了“到时间才能取”的约束。Dijkstra最短路径算法里传统教材用数组找未访问最小距离节点复杂度O(V^2)换成优先队列可以把复杂度降到O(E log V)尤其是在稀疏图上收益明显。哈夫曼编码也离不开优先队列每次从森林里取出权值最小的两棵树合并再放回去重复n-1次。没有堆的话这个“每次取最小”的过程会非常痛苦。6. 源码之外的常见问题与排查技巧读源码只是第一步真正恶心人的是业务代码里踩坑。这一节我把这些年PriorityQueue相关的问题集中整理下很多都是在排查线上问题时才想明白的。6.1 null值、空集合、初始容量过小的坑PriorityQueue不允许null因为堆序依赖比较null无法参与比较。这个从offer方法的第一个if就能看到。如果业务数据里可能混入null一定要在入队前过滤别指望PriorityQueue帮你做防护。另一个坑是new PriorityQueue(5)之后如果你往里塞了6个元素它会自动扩容到11左右5 64走2倍25 - 12。这个自动扩容本身没问题但如果你在构造函数里传入的初始容量是0那就会在第一次offer时触发扩容虽然结果没错但白白多一次拷贝。一般建议传入一个大于0且略高于预期的初始值。还有个容易被忽略的行为toString输出的顺序不是堆序而是数组的物理顺序。比如队列里有1、2、3、4、5打印出来可能是[1, 2, 4, 3, 5]看着像“乱序”。这不是bug这是堆的存储结构决定的。想按序输出得不停poll或者转成数组再排序。6.2 迭代器失效与modCountPriorityQueue的Iterator遍历顺序是数组下标顺序不是优先级顺序。也就是说PriorityQueueInteger pq new PriorityQueue(Arrays.asList(3, 1, 4, 1, 5)); for (Integer x : pq) { System.out.print(x ); // 可能输出 1 3 4 1 5 这类顺序 }这不符合很多人的直觉。想要有序遍历要么转成List再Collections.sort要么循环poll。modCount方面任何add、remove、clear操作都会使它自增迭代器每次next都会检查modCount是否变化变了就抛ConcurrentModificationException。这里有个冷知识扩容本身不会额外改变modCount但offer方法在最前面已经执行了modCount所以迭代器遍历过程中你调一次offer仍然会触发fail-fast。如果你在遍历时确实需要临时添加元素要么先收集到另一个集合里遍历完再统一offer要么改用允许并发修改的容器。6.3 自定义对象排序的Comparator陷阱实际项目里PriorityQueue存的往往是自定义对象这时候Comparator的写法就很重要。我见过几个高频问题第一Comparator返回0不代表元素相等。PriorityQueue允许重复元素Comparator返回0时两个元素只是“优先级相同”它们都会保留在队列里。这和TreeSet直接用compareTo决定去重完全不一样。第二remove(Object)用的是equals不是Comparator。假设你的Comparator认为两个对象“相同”但equals返回false那么remove(A)不会帮你把那个“优先级相同的B”删掉。这种“比较器和equals不一致”导致的诡异现象排查起来特别费劲。第三不要修改已在队列中的对象的比较字段。比如你往队列里放了一个Task对象它的priority字段参与了Comparator比较任务还在队列里时你改了priority堆序就被破坏了。后续poll出来的顺序可能完全错误。这种问题不会报任何异常只能靠代码规范约束对象入队之后参与比较的属性必须不可变真要改先remove再改再offer。另外想实现最大堆最简单的方式是PriorityQueueInteger maxHeap new PriorityQueue(Comparator.reverseOrder());不用自己写比较逻辑一行搞定。7. 面试与实战怎么把这些源码知识转化成自己的产出既然标题里带了“面试题”这个热词最后就聊点实际的。PriorityQueue是Java面试中比较爱考的集合类但很多人只会背“底层是二叉堆小顶堆插入删除O(log n)”这属于及格线。想拿高分得把源码里那些精巧的设计串起来讲。7.1 面试应答思路我建议按这个层次组织回答第一层数据结构。PriorityQueue底层是Object数组逻辑上是一棵完全二叉树默认容量11比较器为null时走自然顺序。第二层核心操作。offer的路径是“先扩容后上浮”siftUp负责把末尾元素向上调整poll的路径是“用末尾元素顶替堆顶再下沉”siftDown负责从根开始向下找合适位置。每次操作O(log n)。第三层动态调整。grow在小容量时2倍2扩容大容量时1.5倍扩容最大容量受MAX_ARRAY_SIZE限制扩容不会破坏堆序因为父子关系只是数组下标的计算规则。第四层细节亮点。比如heapify批量建堆是O(n)不是O(n log n)removeAt在删除任意节点时如果下沉后位置没变还需要上浮回退同优先级元素不保证出队顺序所以它是不稳定排序。能把第四层讲出来基本就能让面试官点头了。如果再能主动举一个TopK或者Dijkstra的落地场景那就不是背八股文而是真的理解了这个数据结构。7.2 我踩过的扩容与性能相关的坑最后分享两个真实经验。第一个是曾经在做一个实时推荐服务时用PriorityQueue维护用户最近的浏览记录用户量一大频繁offer和poll导致GC压力明显。查来查去发现创建PriorityQueue时没有指定初始容量每次扩张都要把旧数组里的元素复制到新数组高峰期每秒几千次扩容拷贝GC自然顶不住。改成按预估并发量设置初始容量后GC曲线立刻平缓很多。另一个是排查过一起“出队顺序错乱”的线上故障最后定位到业务代码里有个对象入队后被人改了排序字段。从那之后我定了一条规矩凡是进PriorityQueue的对象要么把排序字段设成final要么在文档里写死禁止修改。这个教训比读十遍源码都深刻。所以如果你现在正准备Java面试或者只是想把集合源码吃透我给你的建议是不要只盯着结论而是把PriorityQueue拆成“堆排序”和“动态调整”两条主线去读。一条主线是siftUp、siftDown、heapify这些维持堆序的算法另一条主线是grow、MAX_ARRAY_SIZE、hugeCapacity这些动态容量的保障机制。两条线汇合在一起才是这个类真正的全貌。面试官问起来你能从数组下标公式一路聊到扩容溢出处理这才是源码深度解析该有的样子。
Java PriorityQueue源码解析：二叉堆实现与动态调整机制
1. 先弄明白它的设计骨架为什么是数组为什么能保证O(logn)被问到“PriorityQueue底层是什么”时大多数人都能回答出“二叉堆”这三个字。但再追问一句“数组下标和二叉堆节点是怎么对应上的”不少背八股文的朋友就开始卡壳了。这很正常因为PriorityQueue的源码实现里堆从来不是像教科书那样从下标1开始的也没有单独的“节点”对象它就是把一棵完全二叉树直接拍扁到一个Object数组里。1.1 类声明与核心字段先看类结构。PriorityQueue继承自AbstractQueue实现了Serializable字段就五个public class PriorityQueueE extends AbstractQueueE implements java.io.Serializable { private static final int DEFAULT_INITIAL_CAPACITY 11; transient Object[] queue; // 底层数组 private int size 0; // 当前元素个数 private final Comparator? super E comparator; // 比较器可为null transient int modCount; // 结构性修改计数 }这里有几个容易被忽略的信息。queue数组注释明确要求“非空”这个约束很关键。size和queue.length不是一回事queue.length是容量size是实际元素个数。comparator是final的一旦构造确定就不能换了。modCount在Java集合框架里是老熟人PriorityQueue同样用它做fail-fast迭代器保护。重点说说comparator为null的情况。当构造器没有传比较器时PriorityQueue要求元素自身实现Comparable接口入队和出队时会强转成Comparable再比较。如果元素没有实现Comparable运行时抛ClassCastException而不是编译期报错。这个“延迟到运行时才发现”的特性是很多线上问题埋在深处的根源。1.2 数组下标就是一棵完全二叉树PriorityQueue用的是二叉最小堆堆顶永远是优先级最高值最小按comparator规则的元素。它和ArrayList一样用动态数组存数据区别在于数组下标被赋予了“父子关系”下标k的节点的父节点下标(k - 1) 1下标k的节点的左孩子下标(k 1) 1下标k的节点的右孩子下标(k 1) 2很多教材讲堆排序时习惯从下标1开始父节点用k/2这样虽然数学上漂亮但等于浪费了下标0。JDK选择了从0开始的方案省一个数组位还通过位运算替代乘除法性能更优。这个选择也决定了源码里到处是这种看起来有点费解的位移表达式。堆序性质体现在任意父节点都比它的两个子节点“小”。注意这个性质只约束父子之间不约束兄弟节点之间也不保证数组是全局有序的。也就是说你平铺这个数组它不是排好序的但每次弹出堆顶之后能保证剩下部分继续满足堆序。这也是“堆排序”和“普通排序”的核心差异堆维持的是局部有序的偏序关系而不是全序。1.3 默认容量11和比较器的两条分支为什么默认容量是11而不是16这个没查到官方特别权威的说法但可以合理推测JDK作者在写这个类时对“常见业务里队列初始元素数”做了个保守估计11不算大不会太浪费也足够覆盖大部分小规模场景。不过真在代码里用如果明确知道要装多少个元素还是建议显式指定初始容量避免频繁扩容。比较器存在两种模式源码里几乎所有调整方法都成对出现siftUpComparable / siftDownComparable走自然顺序元素必须实现ComparablesiftUpUsingComparator / siftDownUsingComparator走外部Comparator它们在操作上完全等价只是一个用强转后的Comparable自比较一个用comparator字段比较。看源码的时候记着这个规律两个方法读一个就够了另一个套路完全一样。2. 构造器从集合初始化时是怎么瞬间变成堆的很多人在PriorityQueue初始化上栽过跟头。new PriorityQueue(list)之后你以为元素已经排好序了并没有它只是完成了建堆数组看起来仍然“乱糟糟”的。要理解这个得看构造器内部到底走了什么逻辑。2.1 五类构造器入口PriorityQueue提供了多个构造器常见的有这些PriorityQueue() // 默认容量11自然顺序 PriorityQueue(int initialCapacity) // 指定容量自然顺序 PriorityQueue(int initialCapacity, Comparator? super E comparator) PriorityQueue(Collection? extends E c) // 从集合初始化 PriorityQueue(PriorityQueue? extends E c) // 从优先队列拷贝 PriorityQueue(SortedSet? extends E c) // 从有序集合初始化构造器里有个很微妙的分类逻辑当传入的是PriorityQueue或SortedSet时直接走initFromPriorityQueue或initFromSortedSet。因为这两种集合内部元素本身已经满足堆序SortedSet是按升序遍历直接按迭代顺序复制到数组即可无需重建堆。但传入的是普通Collection时就只能先复制出数组再调用heapify来建堆。这个设计体现了JDK对“已知有序来源”的信任和利用能省则省不能省才做重活。2.2 heapifyO(n)建堆而不是O(n log n)heapify是建堆的核心源码很短private void heapify() { for (int i (size 1) - 1; i 0; i--) siftDown(i, (E) queue[i]); }(size 1) - 1算出的是最后一个非叶子节点的下标。比如size10最后一个非叶子节点是下标4。循环从它开始往前逐个执行siftDown下沉直到根节点0。这个方向很讲究只有从下往上调整才能保证处理到某个节点时它的左右子树已经是合法堆这时只需要把当前节点下沉到正确位置即可。很多初学者会想当然地用“逐个offer建堆”那是O(n log n)的复杂度。heapify的妙处在于叶子节点不需要处理越靠近根部的节点数量越少虽然单个节点下沉代价高但总代价被“低频高价”和“高频低价”拉平数学上可以证明整体是O(n)。这是堆排序里最容易被低估的优化点面试时能主动讲出“批量建堆是线性复杂度”会显得你确实读过源码。2.3 从集合转数组的隐藏细节initFromCollection里有个检查容易被忽略private void initFromCollection(Collection? extends E c) { Object[] es c.toArray(); if (es.getClass() ! Object[].class) es Arrays.copyOf(es, es.length, Object[].class); queue es; size es.length; heapify(); }如果传入集合的toArray返回的不是Object[]类型比如TreeSet的toArray可能返回实际类型数组必须用Arrays.copyOf转成Object[]。这一步是为了后续put到queue数组时类型安全。很多自研框架的源码里都有这类防御性拷贝看多了你会发现Java集合类在“类型擦除时代”遗留下来的细节特别多。3. 入队的完整链路siftUp上浮加grow动态扩容“堆排序与动态调整的完美结合”这句话最直观的体现就是在offer方法里。offer承载了两件事把新元素放在堆尾并上浮到正确位置如果数组不够用先扩容再把元素放进去。顺序是先扩容后入堆而不是先塞进去再扩容这个顺序要记清楚。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; }第一步拒绝null。PriorityQueue底层依赖元素比较null没法参与任何比较所以直接抛NPE。第二步modCount。只要发生结构性修改插入、删除、清空这个计数就会变化迭代器靠它实现fail-fast。第三步判断是否需要扩容。这里有个反直觉的点size是当前元素个数它和数组长度相等时新元素下标就是size所以需要grow(size 1)。grow的参数是“所需最小容量”不是“要扩到多大”。第四步是精髓。如果队列原本为空新元素直接放queue[0]当堆顶不需要任何调整如果非空先放在数组末尾下标i处然后调用siftUp(i, e)让它一路向上找家。3.2 siftUp上浮的细节siftUp用“插入排序”的思路维护堆序新元素先坐在数组末尾然后反复和父节点比较如果比父节点小就把父节点往下挪自己继续往上试探直到找到合适位置。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; }注意break条件key.compareTo(parent) 0就停。意思是新元素只要不比父节点小就原地定居。这个条件保证了最小堆性质但同样值时新元素停在较深位置这直接导致了PriorityQueue的不稳定性。后面第5节我会专门演示这个现象。整个上浮过程最坏情况是从叶子一路换到根代价O(log n)。但由于新元素通常随机分布实际平均调整次数远小于树高这也是为什么PriorityQueue在动态数据流场景下比“每次维护一个有序数组”高效得多的根本原因。3.3 grow扩容的数学规则grow是“动态调整”的另一个主角。源码private void grow(int minCapacity) { int oldCapacity queue.length; int newCapacity oldCapacity ((oldCapacity 64) ? (oldCapacity 2) : (oldCapacity 1)); if (newCapacity MAX_ARRAY_SIZE) { newCapacity hugeCapacity(minCapacity); } queue Arrays.copyOf(queue, newCapacity); }这个扩容公式非常有意思。oldCapacity小于64时新容量是 oldCapacity * 2 2。大于等于64时新容量是 oldCapacity oldCapacity / 2也就是1.5倍。我们以默认容量11为例演算一下容量变化11 - 11 * 2 2 2424 - 24 * 2 2 5050 - 50 * 2 2 102102 - 102 51 153153 - 153 76 229看到没前三次接近翻倍之后就变成1.5倍。这个策略和ArrayList类似容量较小时快速翻倍减少扩容次数容量较大时控制增速避免一次性分配过大内存。grow期间要做Arrays.copyOf这是O(n)的数组拷贝但扩容量是倍增的均摊到每次offer上的成本其实很低。还需要提一下MAX_ARRAY_SIZE Integer.MAX_VALUE - 8。源码注释说得很清楚某些虚拟机在数组头部会存一些元信息数组实际最大长度可能比Integer.MAX_VALUE小强行分配太大会直接OutOfMemoryError。hugeCapacity就是兜底逻辑如果minCapacity溢出成负数直接抛OOM否则在MAX_ARRAY_SIZE和Integer.MAX_VALUE之间选择。3.4 扩容和堆调整的配合顺序很多人会觉得“扩容之后数组变了原来的堆结构是不是要重建”。完全不需要。因为堆结构完全靠数组下标之间的父子关系表达元素值不变、下标不变堆序就天然维持。扩容只是把数组复制到一块更大的连续内存上堆的性质不受任何影响。这也是“数组式堆”相比“链式堆”的优势之一扩容成本可控且不会破坏既有堆序。实际操作中我习惯在创建PriorityQueue时如果大概能预估数据量就把初始容量设得稍微宽裕一点。因为扩容终究是一次整数组拷贝数据量大时也会有毫秒级的停顿虽然不如HashMap扩容那么伤但能避免还是尽量避免。4. 出队和删除poll、removeAt与siftDown下沉入队看上浮出队看下沉。如果把PriorityQueue比作一个不断有新人插队的队伍那么出队就是“队长走了后面的人依次往前补位”的过程。但这里有个非常反直觉的设计补位的人不是左孩子或右孩子中的较小者而是数组末尾的最后一个元素。这背后的原因值得深挖。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; }流程分四步把堆顶result保存下来准备返回把数组最后一个元素x取出来将数组末尾置null帮助GC把x放到堆顶位置执行siftDown。为什么不直接让左、右孩子中的较小者当新堆顶因为如果直接把某个孩子提上来这个孩子原来的位置就空出来了还得从它的孩子里再选一个补位一路递归下去实现复杂且容易破坏结构。而把末尾元素提到堆顶虽然它大概率是个较大的值但通过一次下沉操作就能把它压到正确位置只需维护一条从根向下的路径代码干净很多。这也解释了为什么poll是O(log n)本质上是删除根节点后从根开始沿一条路径做下沉路径长度就是树高。peek和poll的区别也提醒一下peek只读queue[0]不修改结构时间复杂度O(1)也不会动modCount。4.2 siftDown下沉的边界判断siftDown的代码比siftUp复杂因为它有两个孩子要比较private void siftDownComparable(int k, E x) { Comparable? super E key (Comparable? super E) x; int half size 1; while (k half) { int child (k 1) 1; 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的节点没有孩子是叶子下沉没必要继续。每轮循环先找左孩子child如果右孩子存在且比左孩子更小就选右孩子为候选c。这一步非常关键下沉时要和孩子中较小者比较否则可能出现“父节点比右孩子大但比左孩子小”的情况导致堆序被破坏。找到较小孩子后如果key不比它大说明当前位置合适break否则把较小的孩子往上挪自己则进入孩子的位置继续下沉。整个过程像气泡往下沉越沉越深直到遇到一个“周围都比我小”的安稳位置。siftDown在堆排序里还承担着另一个使命。堆排序的经典步骤就是“交换堆顶和末尾元素缩小堆长度再从根下沉”PriorityQueue每次poll之后虽然没有交换元素到数组末尾但“从根下沉”的思想和堆排序是完全一致的。可以说PriorityQueue就是“永远只执行堆排序第一步”的数据结构。4.3 removeAt中那个精妙的上浮回退remove(Object o)会先线性扫描找到元素下标再调用removeAt(i)删掉。removeAt的设计比poll复杂得多因为它删除的不一定是堆顶可能是树中间任意位置的节点。private E removeAt(int i) { modCount; int s --size; if (s i) 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; }这段代码最有意思的是先用末尾元素moved填到被删位置i执行siftDown下沉。如果下沉结束后queue[i]还是moved说明moved在整棵子树里已经是最小了。但注意siftDown只关心子树它对“moved是否比父节点小”一无所知。moved是从数组末尾来的它可能非常小小到比父节点还小这时它应该继续“上浮”才对于是源码补了一次siftUp(i, moved)。这个“先下沉如果原地下沉不了再上浮”的双向调整保证了任意位置删除后堆序依然成立。网上不少源码分析文章只讲poll不讲removeAt其实面试里真正的加分点恰恰在这个回退逻辑上。把它讲清楚面试官会觉得你是真的啃过源码。另外注意removeAt的返回值。moved最终停在原地则返回null表示从迭代器视角来看没有元素被“移动到当前迭代位置之前”如果moved上浮到了更靠前的位置返回moved迭代器需要把它记录下来避免漏遍历。这个细节在实现迭代器删除时特别关键。5. 排序稳定性、并发安全与适用场景源码读完了接下来聊点工程层面的问题。PriorityQueue不是银弹它有明确的适用边界也有一个很容易被忽略的排序稳定性问题。5.1 为什么PriorityQueue不是稳定排序先做个实验。定义元素class Item { int value; String name; Item(int value, String name) { this.value value; this.name name; } }按顺序依次入队(1,a)、(2,b)、(1,c)、(0,d)然后依次poll。根据堆调整的路径最终得到的出队顺序很可能是(0,d)、(1,c)、(1,a)、(2,b)。看到问题没有value同为1的两个元素先入队的a反而排到了c后面。原因就在siftUp的break条件key.compareTo(parent) 0就停同值的新元素不会继续上浮穿越旧元素但旧元素可能在后续删除时被末尾元素顶掉位置导致相对顺序被打乱。堆排序本身就是不稳定的排序算法PriorityQueue在Javadoc里也明确写了“对于相等优先级元素不保证FIFO顺序”。如果业务上要求同优先级按入队先后出队必须自定义Comparator把入队序号作为次级排序键。5.2 和TreeMap、Arrays.sort的对比我在项目里见过不少同事在需要“每次取最小值”的场景里直接用了TreeMap或每次排序的ArrayList性能和代码可读性都打了折扣。做个简单对比维度PriorityQueueTreeMap/TreeSet每次Arrays.sort底层结构动态数组 二叉堆红黑树快排/TimSort插入复杂度O(log n)O(log n)每次O(n log n)取最小值O(1) peekO(log n) 拿first排序后O(1)遍历顺序数组顺序不保证有序按键有序完全有序重复元素允许TreeSet去重允许稳定性不稳定不适用/稳定需讨论对象排序稳定PriorityQueue最适合的场景是“动态数据流 只关心极值”。比如无止境地往系统里塞任务每次要优先处理最紧急的一个这种场景它几乎是理想选择。但如果你需要遍历所有元素时都有序那就别用PriorityQueue直接TreeMap或者排序后的ArrayList更合适。5.3 经典场景TopK、定时器、DijkstraPriorityQueue的真实应用遍地都是。最经典的是TopK问题在一个很大的数据流里维护最大的100个数做法就是建一个容量100的最小堆每个新元素如果比堆顶大就poll掉堆顶再offer新元素。这样堆里永远保存着当前最大的100个堆顶就是这100个里最小的那个。ScheduledThreadPoolExecutor内部也有一个基于堆的延迟队列叫DelayedWorkQueue它的结构核心就是优先队列思想只是额外增加了“到时间才能取”的约束。Dijkstra最短路径算法里传统教材用数组找未访问最小距离节点复杂度O(V^2)换成优先队列可以把复杂度降到O(E log V)尤其是在稀疏图上收益明显。哈夫曼编码也离不开优先队列每次从森林里取出权值最小的两棵树合并再放回去重复n-1次。没有堆的话这个“每次取最小”的过程会非常痛苦。6. 源码之外的常见问题与排查技巧读源码只是第一步真正恶心人的是业务代码里踩坑。这一节我把这些年PriorityQueue相关的问题集中整理下很多都是在排查线上问题时才想明白的。6.1 null值、空集合、初始容量过小的坑PriorityQueue不允许null因为堆序依赖比较null无法参与比较。这个从offer方法的第一个if就能看到。如果业务数据里可能混入null一定要在入队前过滤别指望PriorityQueue帮你做防护。另一个坑是new PriorityQueue(5)之后如果你往里塞了6个元素它会自动扩容到11左右5 64走2倍25 - 12。这个自动扩容本身没问题但如果你在构造函数里传入的初始容量是0那就会在第一次offer时触发扩容虽然结果没错但白白多一次拷贝。一般建议传入一个大于0且略高于预期的初始值。还有个容易被忽略的行为toString输出的顺序不是堆序而是数组的物理顺序。比如队列里有1、2、3、4、5打印出来可能是[1, 2, 4, 3, 5]看着像“乱序”。这不是bug这是堆的存储结构决定的。想按序输出得不停poll或者转成数组再排序。6.2 迭代器失效与modCountPriorityQueue的Iterator遍历顺序是数组下标顺序不是优先级顺序。也就是说PriorityQueueInteger pq new PriorityQueue(Arrays.asList(3, 1, 4, 1, 5)); for (Integer x : pq) { System.out.print(x ); // 可能输出 1 3 4 1 5 这类顺序 }这不符合很多人的直觉。想要有序遍历要么转成List再Collections.sort要么循环poll。modCount方面任何add、remove、clear操作都会使它自增迭代器每次next都会检查modCount是否变化变了就抛ConcurrentModificationException。这里有个冷知识扩容本身不会额外改变modCount但offer方法在最前面已经执行了modCount所以迭代器遍历过程中你调一次offer仍然会触发fail-fast。如果你在遍历时确实需要临时添加元素要么先收集到另一个集合里遍历完再统一offer要么改用允许并发修改的容器。6.3 自定义对象排序的Comparator陷阱实际项目里PriorityQueue存的往往是自定义对象这时候Comparator的写法就很重要。我见过几个高频问题第一Comparator返回0不代表元素相等。PriorityQueue允许重复元素Comparator返回0时两个元素只是“优先级相同”它们都会保留在队列里。这和TreeSet直接用compareTo决定去重完全不一样。第二remove(Object)用的是equals不是Comparator。假设你的Comparator认为两个对象“相同”但equals返回false那么remove(A)不会帮你把那个“优先级相同的B”删掉。这种“比较器和equals不一致”导致的诡异现象排查起来特别费劲。第三不要修改已在队列中的对象的比较字段。比如你往队列里放了一个Task对象它的priority字段参与了Comparator比较任务还在队列里时你改了priority堆序就被破坏了。后续poll出来的顺序可能完全错误。这种问题不会报任何异常只能靠代码规范约束对象入队之后参与比较的属性必须不可变真要改先remove再改再offer。另外想实现最大堆最简单的方式是PriorityQueueInteger maxHeap new PriorityQueue(Comparator.reverseOrder());不用自己写比较逻辑一行搞定。7. 面试与实战怎么把这些源码知识转化成自己的产出既然标题里带了“面试题”这个热词最后就聊点实际的。PriorityQueue是Java面试中比较爱考的集合类但很多人只会背“底层是二叉堆小顶堆插入删除O(log n)”这属于及格线。想拿高分得把源码里那些精巧的设计串起来讲。7.1 面试应答思路我建议按这个层次组织回答第一层数据结构。PriorityQueue底层是Object数组逻辑上是一棵完全二叉树默认容量11比较器为null时走自然顺序。第二层核心操作。offer的路径是“先扩容后上浮”siftUp负责把末尾元素向上调整poll的路径是“用末尾元素顶替堆顶再下沉”siftDown负责从根开始向下找合适位置。每次操作O(log n)。第三层动态调整。grow在小容量时2倍2扩容大容量时1.5倍扩容最大容量受MAX_ARRAY_SIZE限制扩容不会破坏堆序因为父子关系只是数组下标的计算规则。第四层细节亮点。比如heapify批量建堆是O(n)不是O(n log n)removeAt在删除任意节点时如果下沉后位置没变还需要上浮回退同优先级元素不保证出队顺序所以它是不稳定排序。能把第四层讲出来基本就能让面试官点头了。如果再能主动举一个TopK或者Dijkstra的落地场景那就不是背八股文而是真的理解了这个数据结构。7.2 我踩过的扩容与性能相关的坑最后分享两个真实经验。第一个是曾经在做一个实时推荐服务时用PriorityQueue维护用户最近的浏览记录用户量一大频繁offer和poll导致GC压力明显。查来查去发现创建PriorityQueue时没有指定初始容量每次扩张都要把旧数组里的元素复制到新数组高峰期每秒几千次扩容拷贝GC自然顶不住。改成按预估并发量设置初始容量后GC曲线立刻平缓很多。另一个是排查过一起“出队顺序错乱”的线上故障最后定位到业务代码里有个对象入队后被人改了排序字段。从那之后我定了一条规矩凡是进PriorityQueue的对象要么把排序字段设成final要么在文档里写死禁止修改。这个教训比读十遍源码都深刻。所以如果你现在正准备Java面试或者只是想把集合源码吃透我给你的建议是不要只盯着结论而是把PriorityQueue拆成“堆排序”和“动态调整”两条主线去读。一条主线是siftUp、siftDown、heapify这些维持堆序的算法另一条主线是grow、MAX_ARRAY_SIZE、hugeCapacity这些动态容量的保障机制。两条线汇合在一起才是这个类真正的全貌。面试官问起来你能从数组下标公式一路聊到扩容溢出处理这才是源码深度解析该有的样子。
