PriorityQueue详解
PriorityQueue 详解：Java 中的优先级队列
PriorityQueue 是 Java 集合框架中基于二叉堆实现的优先级队列，它能够保证每次取出的元素都是队列中优先级最高的（默认是自然排序的最小值）。与普通队列的 “先进先出” 不同，PriorityQueue 的元素顺序由优先级决定，适用于需要动态获取最值的场景（如任务调度、Top K 问题等）。
核心特性
- 底层结构：基于二叉堆（完全二叉树），使用数组存储，空间效率高。
- 排序方式：支持自然排序（元素实现
Comparable）或定制排序（传入Comparator）。 - 无界队列：容量可动态扩容（默认初始容量 11），理论上没有上限（受限于内存）。
- 时间复杂度：插入（
offer）和删除（poll）操作的时间复杂度为O(log n)，获取最值（peek）为O(1)。 - 非线程安全：多线程环境需使用
PriorityBlockingQueue（并发版本）。 - 不允许 null 元素：插入
null会抛出NullPointerException。
底层数据结构：二叉堆
PriorityQueue 的核心是二叉堆，它是一种满足以下性质的完全二叉树：
结构性：是一棵完全二叉树（除最后一层外，每一层都被填满；最后一层的节点靠左排列）。
堆序性：
- 小顶堆（默认）：每个节点的值 ≤ 其左右子节点的值（根节点是最小值）。
graph TD
0((0)) --- 1((1)) --- 3((3))
1((1)) --- 4((4))
0((0)) --- 2((2))
- 大顶堆：每个节点的值 ≥ 其左右子节点的值（根节点是最大值）。
graph TD
0((4)) --- 1((3)) --- 3((1))
1((3)) --- 4((0))
0((4)) --- 2((2))
堆的数组表示
完全二叉树的特性使得堆可以用数组高效存储，父子节点的索引关系如下：
- 对于索引为i的节点：
- 左子节点索引：
2*i + 1 - 右子节点索引：
2*i + 2 - 父节点索引：
(i - 1) >>> 1（等价于(i-1)/2，无符号右移避免负数问题）
- 左子节点索引：
例如，小顶堆的数组表示：
数组：[1, 3, 2, 6, 5, 4]
对应堆结构：
1
/ \
3 2
/ \ /
6 5 4小顶堆与大顶堆
- 小顶堆：根节点是最小值，每次
poll操作取出最小值。 - 大顶堆：根节点是最大值，需通过定制比较器实现（
Comparator.reverseOrder()）。
核心源码解析（JDK 8）
重要属性
// 默认初始容量
private static final int DEFAULT_INITIAL_CAPACITY = 11;
// 存储堆元素的数组（完全二叉树的数组表示）
transient Object[] queue;
// 元素数量
private int size = 0;
// 比较器（null 表示自然排序，默认小顶堆）
private final Comparator<? super E> comparator;
// 修改次数（用于迭代器的 fail-fast 机制）
transient int modCount = 0;
// 最大容量（避免 Integer 溢出）
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;构造函数
PriorityQueue 提供多种构造函数，核心是初始化容量和比较器：
// 1. 默认构造器（初始容量 11，自然排序）
public PriorityQueue() {
this(DEFAULT_INITIAL_CAPACITY, null);
}
// 2. 指定初始容量（自然排序）
public PriorityQueue(int initialCapacity) {
this(initialCapacity, null);
}
// 3. 指定比较器（初始容量 11）
public PriorityQueue(Comparator<? super E> comparator) {
this(DEFAULT_INITIAL_CAPACITY, comparator);
}
// 4. 核心构造器（指定容量和比较器）
public PriorityQueue(int initialCapacity, Comparator<? super E> comparator) {
if (initialCapacity < 1)
throw new IllegalArgumentException();
this.queue = new Object[initialCapacity];
this.comparator = comparator;
}
// 5. 从集合初始化（根据集合类型决定比较器）
public PriorityQueue(Collection<? extends E> c) {
if (c instanceof SortedSet<?>) {
// 从 SortedSet 初始化，复用其比较器
SortedSet<? extends E> ss = (SortedSet<? extends E>) c;
this.comparator = (Comparator<? super E>) ss.comparator();
initElementsFromCollection(ss);
} else if (c instanceof PriorityQueue<?>) {
// 从 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）：将新元素与父节点比较，若不符合堆序则交换，直到满足堆序。
public boolean offer(E e) {
if (e == null)
throw new NullPointerException(); // 不允许 null
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;
// 容量 <64 时，扩容为 old + (old + 2)；否则扩容 50%
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）：将堆顶元素与子节点比较，若不符合堆序则交换，直到满足堆序。
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. 自然排序（小顶堆）
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(3);
pq.offer(1);
pq.offer(2);
System.out.println(pq.peek()); // 1（堆顶是最小值）
while (!pq.isEmpty()) {
System.out.print(pq.poll() + " "); // 1 2 3（按优先级出队）
}2. 定制排序（大顶堆）
// 使用 Comparator 实现大顶堆
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
maxHeap.offer(3);
maxHeap.offer(1);
maxHeap.offer(2);
System.out.println(maxHeap.peek()); // 3（堆顶是最大值）
while (!maxHeap.isEmpty()) {
System.out.print(maxHeap.poll() + " "); // 3 2 1
}3. 自定义对象排序
class Student implements Comparable<Student> {
String name;
int score;
public Student(String name, int score) {
this.name = name;
this.score = score;
}
// 按分数升序排序（自然排序）
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); // Bob（80）→ Alice（90）→ Charlie（95）
}注意事项
- 迭代顺序不保证有序：
PriorityQueue的迭代器（iterator()）不按优先级顺序遍历，若需有序遍历，需多次调用poll()方法。 - 扩容策略：初始容量 11，当容量 <64 时每次扩容增加
old + 2，否则增加 50%，避免频繁扩容。 - 与
TreeSet的区别：PriorityQueue是队列，允许重复元素；TreeSet是集合，不允许重复，且全量有序。PriorityQueue侧重动态获取最值；TreeSet侧重范围查询和全量排序