PriorityQueue

一、概念与基本特性

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

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

二、源码结构与数据字段

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

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 操作（向上堆化）

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

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 操作（向下堆化）

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

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

五、扩容机制

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

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

七、比较器支持

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

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

八、遍历与非排序

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

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

但 遍历顺序不是堆序或有序，只是按数组顺序遍历底层数组。若需要有序输出，应反复 poll()。

⬅️ ArrayDeque 🏠 00-Java ➡️ 00-Map总览