Java 優先級隊列 PriorityQueue 深度解析：從原理到源碼

基本概念

PriorityQueue 是 Java 中基於堆實現的優先級隊列。它實現了 Queue 接口，隊列長度無限制，核心特點是：隊頭元素始終是優先級最高的。內部元素並非完全有序，但逐個出隊可獲得有序輸出。

除了作為優先級隊列，PriorityQueue 還可作為通用堆數據結構，解決適合用堆處理的問題（如 Top-K、中位數維護等）。

基本用法

Queue 接口回顧

public interface Queue<E> extends Collection<E> {
    boolean add(E e);      // 添加，失敗拋異常
    boolean offer(E e);    // 添加，失敗返回 false
    E remove();            // 移除並返回頭部，空拋異常
    E poll();              // 移除並返回頭部，空返回 null
    E element();           // 查看頭部，空拋異常
    E peek();              // 查看頭部，空返回 null
}

構造方法

public PriorityQueue()                              // 默認容量 11，自然順序
public PriorityQueue(int initialCapacity)           // 指定初始容量
public PriorityQueue(int initialCapacity, Comparator<? super E> comparator) // 自定義比較器
public PriorityQueue(Collection<? extends E> c)     // 從集合構建
public PriorityQueue(PriorityQueue<? extends E> c)  // 複製構造
public PriorityQueue(SortedSet<? extends E> c)      // 從有序集合構建

順序要求： 前三個構造要求元素實現 Comparable；第三個可傳 Comparator；後兩個沿用參數容器的比較器，若為 null 則需元素實現 Comparable。

基礎示例

Queue<Integer> pq = new PriorityQueue<>();
pq.offer(10);
pq.add(22);
pq.addAll(Arrays.asList(11, 12, 34, 2, 7, 4, 15, 12, 8, 6, 19, 13));

while (pq.peek() != null) {
    System.out.print(pq.poll() + " ");
}
// 輸出：2 4 6 7 8 10 11 12 12 13 15 19 22 34 (升序)

若需降序，傳入逆序比較器：

Queue<Integer> pq = new PriorityQueue<>(11, Collections.reverseOrder());
// 輸出：34 22 19 15 13 12 12 11 10 8 7 6 4 2

任務隊列實戰

static class Task {
    int priority; String name;
    public Task(int priority, String name) { this.priority = priority; this.name = name; }
    public int getPriority() { return priority; }
    public String getName() { return name; }
}

private static Comparator<Task> taskComparator = (o1, o2) -> {
    if (o1.getPriority() > o2.getPriority()) return -1;
    else if (o1.getPriority() < o2.getPriority()) return 1;
    return 0;
};

Queue<Task> tasks = new PriorityQueue<>(11, taskComparator);
tasks.offer(new Task(20, "寫日記"));
tasks.offer(new Task(10, "看電視"));
tasks.offer(new Task(100, "寫代碼"));

Task task;
while ((task = tasks.poll()) != null) {
    System.out.println("處理任務: " + task.getName() + "，優先級:" + task.getPriority());
}
// 輸出按優先級從高到低：寫代碼(100) → 寫日記(20) → 看電視(10)

源碼實現原理

內部結構

private transient Object[] queue;  // 底層數組
private int size = 0;              // 當前元素數
private final Comparator<? super E> comparator; // 比較器
private transient int modCount = 0; // 修改次數（fail-fast）

擴容機制

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

小數組翻倍，大數組增長 50%。

入隊

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

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

private void siftUpUsingComparator(int k, E x) {
    while (k > 0) {
        int parent = (k - 1) >>> 1;
        Object e = queue[parent];
        if (comparator.compare(x, (E) e) >= 0) break;
        queue[k] = e;
        k = parent;
    }
    queue[k] = x;
}

新元素置於末尾，不斷與父節點比較上浮，直到滿足堆性質。

查看隊頭

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

O(1) 時間複雜度。

出隊

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; // 幫助 GC
    if (s != 0) siftDown(0, x);
    return result;
}

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

取出堆頂，將末尾元素移至堆頂下沉調整。

查找與刪除指定元素

public boolean contains(Object o) { return indexOf(o) != -1; }

private int indexOf(Object o) {
    if (o != null) for (int i = 0; i < size; i++) if (o.equals(queue[i])) return i;
    return -1;
}

public boolean remove(Object o) {
    int i = indexOf(o);
    if (i == -1) return false;
    removeAt(i);
    return true;
}

private E removeAt(int i) {
    modCount++;
    int s = --size;
    if (s == i) queue[i] = null;
    else {
        E moved = (E) queue[s];
        queue[s] = null;
        siftDown(i, moved);
        if (queue[i] == moved) { // 沒下沉，嘗試上浮
            siftUp(i, moved);
            if (queue[i] != moved) return moved;
        }
    }
    return null;
}

查找 O(N)，刪除需先查找再調整堆。

堆構建

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

從最後一個非葉節點自底向上構建堆，O(N) 複雜度。

性能特點總結

• 查看隊頭：O(1)
• 入隊/出隊：O(log N)
• 構建堆：O(N)
• 查找/按值刪除：O(N)
• 內部元素非完全有序，僅保證堆性質
• 允許優先級相同，不保證相同優先級元素的順序

小結

PriorityQueue 是 Java 中堆的標準實現，既可作為優先級隊列，也可作為通用堆結構解決算法問題。下一節將探討其在具體問題中的應用場景。

---------------

關注「老馬說編程」微信公眾號，從入門到高級，深入淺出探索 Java 編程本質。