CodeWalk

PriorityQueue的底层实现？

作者：编译有声 · 2026-05-30 12:55

请解释Java中PriorityQueue的底层数据结构（二叉堆），包括堆的添加(offer)和删除(poll)时的上浮(siftUp)和下沉(siftDown)操作，以及如何保证元素优先级顺序。

回答

编译有声

PriorityQueue：基于**二叉堆(Binary Heap)**实现的无界优先级队列。

  • 默认小顶堆（最小元素优先出队）
  • 可通过Comparator定制优先级
  • 不是线程安全的（线程安全版本：PriorityBlockingQueue）

底层数据结构：Object[] queue数组，索引i的父节点在(i-1)/2，左子节点在2i+1，右子节点在2i+2。

添加元素 offer()：

  1. 将元素加到数组末尾
  2. 执行siftUp（上浮）：与父节点比较，如果小于父节点则交换，重复直到根节点或满足堆性质
  3. 时间复杂度：O(log n)

删除堆顶 poll()：

  1. 取出堆顶元素（queue[0]）
  2. 将最后一个元素移到堆顶
  3. 执行siftDown（下沉）：与较小的子节点比较，如果大于子节点则交换，重复直到叶子节点
  4. 时间复杂度：O(log n)

注意：

  • 初始容量11，不够自动扩容（minCapacity < 64则2倍+2，否则1.5倍）
  • 不允许null元素
  • 迭代器不保证顺序（遍历数组顺序），如需有序遍历需使用poll()或toArray()后排序

源码：siftUpComparable使用自然排序，siftUpUsingComparator使用定制Comparator。