PriorityQueue 详解：Java 中的优先级队列
PriorityQueue 是 Java 集合框架中基于二叉堆实现的优先级队列，它能够保证每次取出的元素都是队列中优先级最高的（默认是自然排序的最小值）。与普通队列的 “先进先出” 不同，PriorityQueue 的元素顺序由优先级决定，适用于需要动态获取最值的场景（如任务调度、Top K 问题等）。
核心特性
- 底层结构：基于二叉堆（完全二叉树），使用数组存储，空间效率高。
- 排序方式：支持自然排序（元素实现
Comparable）或定制排序（传入 Comparator）。
- 无界队列：容量可动态扩容（默认初始容量 11），理论上没有上限（受限于内存）。
- 时间复杂度：插入（
offer）和删除（poll）操作的时间复杂度为 O(log n)，获取最值（peek）为 O(1)。
- 非线程安全：多线程环境需使用
PriorityBlockingQueue（并发版本）。
- 不允许 null 元素：插入
null 会抛出 NullPointerException。
底层数据结构：二叉堆
PriorityQueue 的核心是二叉堆，它是一种满足以下性质的完全二叉树：
结构性：是一棵完全二叉树（除最后一层外，每一层都被填满；最后一层的节点靠左排列）。
堆序性：
- 小顶堆（默认）：每个节点的值 ≤ 其左右子节点的值（根节点是最小值）。
<pre class="mermaid"> graph TD
0((0)) --- 1((1)) --- 3((3))
1((1)) --- 4((4))
0((0)) --- 2((2))</pre>
- 大顶堆：每个节点的值 ≥ 其左右子节点的值（根节点是最大值）。
<pre class="mermaid"> graph TD
0((4)) --- 1((3)) --- 3((1))
1((3)) --- 4((0))
0((4)) --- 2((2))</pre>
堆的数组表示
完全二叉树的特性使得堆可以用数组高效存储，父子节点的索引关系如下：
- 对于索引为i的节点：
- 左子节点索引：
2*i + 1
- 右子节点索引：
2*i + 2
- 父节点索引：
(i - 1) >>> 1（等价于 (i-1)/2，无符号右移避免负数问题）
例如，小顶堆的数组表示：
1
2
3
4
5
6
7
| 数组：[1, 3, 2, 6, 5, 4]
对应堆结构：
1
/ \
3 2
/ \ /
6 5 4
|
小顶堆与大顶堆
- 小顶堆：根节点是最小值，每次
poll 操作取出最小值。
- 大顶堆：根节点是最大值，需通过定制比较器实现（
Comparator.reverseOrder()）。
核心源码解析（JDK 8）
重要属性
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
private static final int DEFAULT_INITIAL_CAPACITY = 11;
transient Object[] queue;
private int size = 0;
private final Comparator<? super E> comparator;
transient int modCount = 0;
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
|
构造函数
PriorityQueue 提供多种构造函数，核心是初始化容量和比较器：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
|
public PriorityQueue() {
this(DEFAULT_INITIAL_CAPACITY, null);
}
public PriorityQueue(int initialCapacity) {
this(initialCapacity, null);
}
public PriorityQueue(Comparator<? super E> comparator) {
this(DEFAULT_INITIAL_CAPACITY, comparator);
}
public PriorityQueue(int initialCapacity, Comparator<? super E> comparator) {
if (initialCapacity < 1)
throw new IllegalArgumentException();
this.queue = new Object[initialCapacity];
this.comparator = comparator;
}
public PriorityQueue(Collection<? extends E> c) {
if (c instanceof SortedSet<?>) {
SortedSet<? extends E> ss = (SortedSet<? extends E>) c;
this.comparator = (Comparator<? super E>) ss.comparator();
initElementsFromCollection(ss);
} else if (c instanceof PriorityQueue<?>) {
PriorityQueue<? extends E> pq = (PriorityQueue<? extends E>) c;
this.comparator = (Comparator<? super E>) pq.comparator();
initFromPriorityQueue(pq);
} else {
this.comparator = null;
initFromCollection(c);
}
}
|
核心操作：插入（offer）
插入元素时，需维持堆的性质（小顶堆或大顶堆），步骤如下：
- 扩容（若数组已满）；
- 将元素插入数组末尾；
- 向上调整（
siftUp）：将新元素与父节点比较，若不符合堆序则交换，直到满足堆序。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| 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;
}
private void grow(int minCapacity) {
int oldCapacity = queue.length;
int newCapacity = oldCapacity + ((oldCapacity < 64) ?
(oldCapacity + 2) :
(oldCapacity >> 1));
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
queue = Arrays.copyOf(queue, newCapacity);
}
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;
}
|
示例：向小顶堆 [1,3,2] 插入元素 0
- 插入末尾：
[1,3,2,0]
- 向上调整：
0（索引 3）的父节点是 3（索引 1），0 < 3 → 交换 → [1,0,2,3]0（索引 1）的父节点是 1（索引 0），0 < 1 → 交换 → [0,1,2,3]
- 结果：
[0,1,2,3]（满足小顶堆）
核心操作：删除（poll）
删除堆顶元素（优先级最高的元素），步骤如下：
- 取出堆顶元素；
- 将数组末尾元素移到堆顶；
- 向下调整（
siftDown）：将堆顶元素与子节点比较，若不符合堆序则交换，直到满足堆序。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| 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;
}
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;
}
|
示例：从小顶堆 [0,1,2,3] 中 poll 元素
- 取出堆顶
0，末尾元素 3 移到堆顶 → [3,1,2,null]
- 向下调整：
3（索引 0）的左右子节点为 1（索引 1）和 2（索引 2），选择较小的 1 → 3 > 1 交换 → [1,3,2,null]3（索引 1）的左右子节点为 3（索引 3，已空），停止调整。
- 结果：
[1,3,2]（满足小顶堆），返回 0
其他常用方法
peek()：获取堆顶元素（不删除），直接返回 queue[0]。remove(Object o)：删除指定元素，需先遍历数组找到索引，再通过 removeAt 方法删除并调整堆。size()：返回元素数量 size。
使用示例
1. 自然排序（小顶堆）
1
2
3
4
5
6
7
8
9
| PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(3);
pq.offer(1);
pq.offer(2);
System.out.println(pq.peek());
while (!pq.isEmpty()) {
System.out.print(pq.poll() + " ");
}
|
2. 定制排序（大顶堆）
1
2
3
4
5
6
7
8
9
10
|
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
maxHeap.offer(3);
maxHeap.offer(1);
maxHeap.offer(2);
System.out.println(maxHeap.peek());
while (!maxHeap.isEmpty()) {
System.out.print(maxHeap.poll() + " ");
}
|
3. 自定义对象排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| class Student implements Comparable<Student> {
String name;
int score;
public Student(String name, int score) {
this.name = name;
this.score = score;
}
@Override
public int compareTo(Student o) {
return Integer.compare(this.score, o.score);
}
}
PriorityQueue<Student> students = new PriorityQueue<>();
students.offer(new Student("Alice", 90));
students.offer(new Student("Bob", 80));
students.offer(new Student("Charlie", 95));
while (!students.isEmpty()) {
System.out.println(students.poll().name);
}
|
注意事项
- 迭代顺序不保证有序：
PriorityQueue 的迭代器（iterator()）不按优先级顺序遍历，若需有序遍历，需多次调用 poll() 方法。
- 扩容策略：初始容量 11，当容量 <64 时每次扩容增加
old + 2，否则增加 50%，避免频繁扩容。
- 与
TreeSet 的区别：
PriorityQueue 是队列，允许重复元素；TreeSet 是集合，不允许重复，且全量有序。PriorityQueue 侧重动态获取最值；TreeSet 侧重范围查询和全量排序