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 维持堆序：

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

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

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

核心成员变量

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

源码分析

写入：offer（上浮 siftUp）

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）

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)。

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

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（按优先级出队）
        }
    }
}