---
title: "02-PriorityQueue"
created: 2025-12-02
tags:
  - Java
---
# PriorityQueue

> [!note] 定位说明
> Queue 系列第 2 篇详篇。最小堆落地：offer/poll 的上浮下沉、数组扩容、Comparator 定制排序。刷题高频（Top K、合并 K 链表、Dijkstra）。

## 一、概念与基本特性

`PriorityQueue<E>` 是一个基于堆（最小堆）实现的优先级队列，元素按照 **优先级升序排列**，每次出队返回最小元素（peek/poll
返回堆顶元素）。

- 底层结构：动态数组 `Object[] queue` 作为二叉堆容器；
- 默认构建的是**最小堆**；
- 插入复杂度 O(log n)，删除堆顶复杂度 O(log n)，访问堆顶 O(1)；
- 支持自定义比较器（`Comparator`）或元素自身实现 `Comparable` 接口；
- 非线程安全；
- 不允许插入 null。

## 二、源码结构与数据字段

```java
public class PriorityQueue<E> extends AbstractQueue<E>
        implements java.io.Serializable {
    transient Object[] queue; // 堆容器，数组实现
    private int size = 0;     // 实际元素数量
    private final Comparator<? super E> comparator; // 自定义比较器
    ...
}
```

- `queue[]`：底层使用数组保存堆结构；
- `size`：记录当前元素个数；
- `comparator`：可选比较器；若为空，则元素必须实现 `Comparable`。

## 三、添加元素：offer() / add()

```java
public boolean offer(E e) {
    if (e == null) throw new NullPointerException();
    int i = size;
    if (i >= queue.length) grow(i + 1); // 扩容
    siftUp(i, e); // 向上调整，维护堆
    size = i + 1;
    return true;
}
```

### siftUp 操作（向上堆化）

```java
private void siftUp(int k, E x) {
    if (comparator != null)
        siftUpUsingComparator(k, x);
    else
        siftUpComparable(k, x);
}
```

对于最小堆，插入新元素后从当前位置向上比较并交换，直到满足“父节点 ≤ 当前节点”规则。

示例结构变更（最小堆）：

```
插入前：  [2, 5, 3]
插入 1：  [1, 2, 3, 5] // 1 向上堆化，成为新堆顶
```

## 四、删除元素：poll()

```java
public E poll() {
    if (size == 0)
        return null;
    int s = --size;
    E result = (E) queue[0];
    E x = (E) queue[s];
    queue[s] = null;
    if (s != 0)
        siftDown(0, x); // 末尾元素替换堆顶后下沉
    return result;
}
```

### siftDown 操作（向下堆化）

```java
private void siftDown(int k, E x) {
    if (comparator != null)
        siftDownUsingComparator(k, x);
    else
        siftDownComparable(k, x);
}
```

删除堆顶元素后，将末尾元素放到堆顶并进行向下调整，保证堆有序性。

## 五、扩容机制

默认初始容量为 11，扩容策略参考 `ArrayList`，约为原容量的 1.5 倍：

```java
private void grow(int minCapacity) {
    int oldCapacity = queue.length;
    int newCapacity = oldCapacity + ((oldCapacity < 64) ?
        (oldCapacity + 2) : // 小数组加倍
        (oldCapacity >> 1)); // 大数组按 1.5 倍扩容
    queue = Arrays.copyOf(queue, newCapacity);
}
```

- 扩容后旧数组内容通过 `Arrays.copyOf` 拷贝，成本为 O(n)。

## 六、最小堆如何维护？

核心在于每次插入或删除后通过 **siftUp / siftDown** 调整元素顺序，确保满足：

> `queue[i] <= queue[2i+1] && queue[i] <= queue[2i+2]`（父节点小于等于左右子节点）

最小堆可以视为完全二叉树，每个节点的下标与其子节点的下标满足：

- 左子节点下标：`2 * i + 1`
- 右子节点下标：`2 * i + 2`
- 父节点下标：`(i - 1) / 2`

## 七、比较器支持

```java
PriorityQueue<Integer> pq = new PriorityQueue<>(); // 默认升序
PriorityQueue<Integer> pq2 = new PriorityQueue<>((a, b) -> b - a); // 自定义降序
```

如果自定义了 `Comparator`，所有堆调整操作都会使用传入的规则，而不是元素本身的 `compareTo()`。

## 八、遍历与非排序

虽然 `PriorityQueue` 实现了 `Iterable` 接口，可以用增强 for 循环遍历：

```java
for (Integer i : pq) {
    System.out.println(i);
}
```

但 **遍历顺序不是堆序或有序**，只是按数组顺序遍历底层数组。若需要有序输出，应反复 poll()。
---
⬅️ [[01-ArrayDeque|ArrayDeque]] 🏠 [[00-Java|00-Java]] ➡️ [[00-Map总览|00-Map总览]]