---
url: https://www.chenlj.top/md/java-base/collections/PriorityQueue.md
---
# PriorityQueue 源码解析

## 简介

`PriorityQueue` 是基于**二叉堆（binary heap）**的优先队列：元素出队顺序不是「入队顺序」，而是按**优先级**（由 `Comparable` 或 `Comparator` 决定，默认是「最小元素优先」的**小顶堆**）。

* 不是线程安全的；并发优先队列请用 `PriorityBlockingQueue`。
* **不允许 `null`**（无法与「最小」比较）。
* 入队 / 出队（调整堆）的复杂度都是 **O(log n)**，`peek` / `size` 是 O(1)；`iterator` 不保证按优先级顺序遍历。
* 底层是一个**可扩容的数组**实现的完全二叉树，用「下标关系」表达父子：节点 `i` 的左子为 `2i+1`，右子为 `2i+2`，父为 `(i-1)/2`。

> 常用于「Top K」、「任务调度」等需要不断取最小/最大元素的场景。

## 底层数据结构分析

`PriorityQueue` 用 `Object[] queue` 以**层序**存储完全二叉树，并依靠 `siftUp` / `siftDown` 维持堆序：

```java
transient Object[] queue;                 // 层序存储的二叉堆
private int size;                         // 元素个数
private final Comparator<? super E> comparator; // 为 null 则用自然顺序
```

父子下标关系（无需额外指针，节省内存）：

```
父节点 i       子节点 2i+1（左）、2i+2（右）
子节点 i       父节点 (i-1)/2
```

## 核心成员变量

```java
transient Object[] queue;                  // 二叉堆数组
private int size = 0;                      // 元素数量
private final Comparator<? super E> comparator; // 比较器（可空）
```

## 源码分析

### 写入：offer（上浮 siftUp）

```java
public boolean offer(E e) {
    if (e == null) throw new NullPointerException(); // 不允许 null
    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 siftUp(int k, E x) {
    if (comparator != null) siftUpUsingComparator(k, x, comparator);
    else {
        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;
    }
}
```

### 读取：poll（下沉 siftDown）

```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;
}

// 下沉：与较小的子节点比较，比子大就交换，直到满足堆序
private void siftDown(int k, E x) {
    if (comparator != null) siftDownUsingComparator(k, x, comparator);
    else {
        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;
    }
}
```

### 建堆：heapify

一次性把无序数组调整为堆（从最后一个非叶子节点向前 `siftDown`），复杂度 O(n)。

```java
private void heapify() {
    for (int i = (size >>> 1) - 1; i >= 0; i--)
        siftDown(i, (E) queue[i]);
}
```

## 与 ArrayDeque / LinkedList 的对比

| 维度 | ArrayDeque | LinkedList | PriorityQueue |
| --- | --- | --- | --- |
| 出队顺序 | 入队顺序 | 入队顺序 | **按优先级** |
| 结构 | 循环数组 | 链表 | 二叉堆（数组） |
| 入/出队 | O(1) | O(1) | O(log n) |
| 允许 null | 否 | 允许 | 否 |
| 范围遍历有序 | 是 | 是 | 否（需逐个 poll） |

## 经典 Demo

```java
import java.util.PriorityQueue;

public class PriorityQueueDemo {
    public static void main(String[] args) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(); // 小顶堆
        pq.add(5); pq.add(1); pq.add(3);
        while (!pq.isEmpty()) {
            System.out.print(pq.poll() + " "); // 1 3 5（按优先级出队）
        }
    }
}
```