Java集合-PriorityQueue

前言

PriorityQueue 是 Java 集合框架中的一种基于 优先级堆（Priority Heap） 实现的队列，位于 java.util 包下。它是一个 无界队列，但具有内部容量限制（会动态扩容）。
与普通队列（如 FIFO 的 LinkedList）不同，PriorityQueue 中的元素会根据 自然顺序（Natural Ordering）或自定义比较器（Comparator） 进行排序，优先级最高的元素（通常是最小的）会优先出队。

源码分析

PriorityQueue 的源码位于 JDK 的 java.util.PriorityQueue 类中，下面从关键点入手分析。

成员变量

private static final int DEFAULT_INITIAL_CAPACITY = 11; // 默认初始容量
private transient Object[] queue; // 存储元素的数组
private int size = 0; // 元素个数
private final Comparator<? super E> comparator; // 自定义比较器
private transient int modCount = 0; // 修改次数，用于快速失败

queue：底层是一个对象数组，存储堆的元素。
size：当前堆中的元素数量。
comparator：用于指定元素比较规则，如果为 null，则使用元素的自然顺序（需要实现 Comparable 接口）。

构造方法

PriorityQueue 提供了多种构造方法，以下是几个典型的：

// 默认构造方法使用容量11，且无比较器
public PriorityQueue() {
    this(DEFAULT_INITIAL_CAPACITY, null);
}

// 可以指定初始容量或自定义比较器
public PriorityQueue(int initialCapacity) {
    this(initialCapacity, null);
}

public PriorityQueue(int initialCapacity, Comparator<? super E> comparator) {
    if (initialCapacity < 1)
        throw new IllegalArgumentException();
    this.queue = new Object[initialCapacity];
    this.comparator = comparator;
}

核心方法

对于 PriorityQueue 来说，其核心方法有：入队、上浮、下沉、出队、扩容。

入队（`offer`）

public boolean offer(E e) {
    if (e == null)
        throw new NullPointerException();
    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;
}

步骤解析：

检查元素是否为 null（不允许 null 元素）。
如果数组容量不足，调用 grow 方法扩容。
如果是第一个元素，直接放在数组首位（堆顶）。
否则调用 siftUp 方法，将新元素上浮到合适位置，维持堆性质。

上浮方法（`siftUp`）

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

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; // 插入新元素
}

使用无符号右移（>>>）计算父节点索引。
通过比较新元素与父节点的大小，逐步上浮，直到满足堆性质。

出队（`poll`）

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

步骤解析：

如果队列为空，返回 null。
取出堆顶元素（最小值），并将最后一个元素移到堆顶。
调用 siftDown 方法调整堆。

下沉方法（`siftDown`）

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

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

通过比较父节点与较小的子节点，逐步下沉，维持小顶堆性质。

扩容（`grow`）

private void grow(int minCapacity) {
    int oldCapacity = queue.length;
    int newCapacity = oldCapacity + ((oldCapacity < 64) ?
                                    (oldCapacity + 2) :
                                    (oldCapacity >> 1));
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    queue = Arrays.copyOf(queue, newCapacity);
}

扩容策略：

如果旧容量小于 64，则新容量为 oldCapacity + 2。
否则，新容量为 oldCapacity * 1.5（右移 1 位相当于除以 2，再加上原容量）。
确保不超过数组最大容量限制。

实现原理

PriorityQueue 底层是一个二叉堆，存储在数组中：

父节点索引：(i - 1) / 2
左子节点索引：2 * i + 1
右子节点索引：2 * i + 2

通过这种映射关系，PriorityQueue 将树形结构扁平化存储在数组中，节省空间并提高效率。

后记

特性

基于堆的数据结构：底层使用小顶堆（Min-Heap）实现，默认情况下，最小元素位于堆顶。
无界性：理论上可以无限添加元素，但内部数组容量会动态扩容。
非线程安全：PriorityQueue 不是线程安全的，如果需要线程安全，可以使用 PriorityBlockingQueue。

时间复杂度

入队（offer）：$O(log n)$
出队（poll）：$O(log n)$
查看堆顶元素（peek）：$O(1)$
删除任意元素（remove）：$O(n)$

使用场景

任务调度：需要按优先级处理任务时。
图算法：如Dijkstra算法的最短路径计算。
数据排序：需要动态维护一个有序集合时。

总结

PriorityQueue 是一个高效的优先级队列实现，基于小顶堆，通过动态调整堆结构保证元素按优先级排序。源码中，siftUp 和 siftDown 是维护堆性质的核心，扩容机制则保证了无界性。