PriorityQueue 源码分析

JavaJuice约 1369 字大约 5 分钟

PriorityQueue 是 Java 中的一个优先级队列实现，基于堆数据结构实现。它提供了一种按照元素的自然顺序或指定的 Comparator 顺序来排序队列中的元素的方式。与 ArrayList 和 LinkedList 不同，PriorityQueue 中的元素是按照优先级排列的，即队列中的最小（或最大）元素始终位于队头。PriorityQueue 常用于需要优先级排序的场景，如任务调度系统。

PriorityQueue 是一个 无界队列，它的容量会根据需要自动扩展。默认情况下，队列中的元素会根据它们的自然顺序进行排序。如果提供了自定义的 Comparator，则根据指定的比较规则进行排序。

2. 主要成员变量

private Object[] queue;
private int size;
private final Comparator<? super E> comparator;
private static final int DEFAULT_INITIAL_CAPACITY = 11;

queue：用来存储元素的数组，底层实现是一个动态数组。
size：队列中当前元素的数量。
comparator：用于元素比较的 Comparator，如果没有提供，则使用元素的自然顺序进行比较。
DEFAULT_INITIAL_CAPACITY：默认队列初始容量，默认为 11。

3. 构造方法

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()：使用默认容量和自然顺序构造队列。
PriorityQueue(int initialCapacity)：使用指定的初始容量构造队列，按照自然顺序排序。
PriorityQueue(int initialCapacity, Comparator<? super E> comparator)：使用指定的初始容量和自定义的比较器构造队列。

4. 内部实现细节

PriorityQueue 底层使用一个堆来存储元素。Java 中的堆通常是一个 完全二叉树，堆的根节点总是最小（或最大）元素。通过堆来实现优先级队列，保证入队和出队操作的时间复杂度是 O(log n)。

堆的操作通过以下几个方法实现：

上浮（heapify-up）：将新插入的元素移动到堆的正确位置。
下沉（heapify-down）：当堆顶元素被移除时，将堆的最后一个元素移动到堆顶，并下沉到合适的位置。

4.1 入队操作：`offer`

public boolean offer(E e) {
    if (e == null) throw new NullPointerException();
    ensureCapacity(size + 1); // 确保容量足够
    queue[size++] = e;
    siftUp(size - 1);  // 上浮新加入的元素
    return true;
}

步骤：
1. 如果元素为 null，抛出 NullPointerException。
2. 调用 ensureCapacity 方法确保堆的容量足够。
3. 将元素放入数组的末尾，并增加队列的大小 (size)。
4. 调用 siftUp 方法将新插入的元素上浮，确保堆的性质被满足。
siftUp 方法：

private void siftUp(int k) {
    Comparable<? super E> key = (Comparable<? super E>) queue[k];
    while (k > 0) {
        int parent = (k - 1) >> 1;
        Object e = queue[parent];
        if (key.compareTo(e) >= 0) break;
        queue[k] = e;
        k = parent;
    }
    queue[k] = key;
}

步骤：
- 上浮操作通过不断与父节点比较并交换位置来保持堆的性质。如果当前节点比父节点小，则交换它们，直到堆的性质满足。
- 上浮操作的时间复杂度是 O(log n)。

4.2 出队操作：`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 (size != 0)
        siftDown(0, x);  // 将堆顶元素移除后，将最后一个元素下沉到合适的位置
    return result;
}

步骤：
1. 如果队列为空，返回 null。
2. 将队列的最后一个元素替换到堆顶。
3. 调用 siftDown 方法将新的堆顶元素下沉，恢复堆的性质。
siftDown 方法：

private void siftDown(int k, 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(queue[right]) > 0)
            c = queue[child = right];
        if (((Comparable<? super E>) x).compareTo(c) <= 0)
            break;
        queue[k] = c;
        k = child;
    }
    queue[k] = x;
}

步骤：
- 下沉操作通过与子节点的比较，将堆顶元素下沉到合适的位置，保持堆的性质。
- 下沉操作的时间复杂度是 O(log n)。

5. 其他方法

peek：返回队列头部的元素（即优先级最高的元素），但不移除它。如果队列为空，返回 null。

public E peek() {
    return (size == 0) ? null : (E) queue[0];
}

remove(Object o)：移除队列中首次出现的指定元素，如果队列中有多个相同的元素，只会移除第一个匹配的元素。

public boolean remove(Object o) {
    if (o == null) return false;
    for (int i = 0; i < size; i++) {
        if (o.equals(queue[i])) {
            fastRemove(i);
            return true;
        }
    }
    return false;
}

clear：清空队列，移除所有元素。

public void clear() {
    Arrays.fill(queue, 0, size, null);
    size = 0;
}

6. 性能特性

插入操作（offer）：时间复杂度为 O(log n)，因为每次插入都需要进行上浮操作。
删除操作（poll）：时间复杂度为 O(log n)，因为每次删除队头元素后需要进行下沉操作。
查找操作（peek）：时间复杂度为 O(1)，直接返回队头元素。
其他操作（remove、clear 等）：时间复杂度为 O(n)，因为需要遍历队列。

总结

PriorityQueue 是一个基于堆实现的优先级队列，具有良好的性能和灵活性。它能够根据元素的自然顺序或指定的 Comparator 对元素进行排序，并提供高效的插入、删除和查找操作。由于它是一个无界队列，能够根据需要动态扩展容量。它在任务调度、路径搜索等场景中具有广泛的应用。