Java 集合深度系列（五）：PriorityQueue 源碼級剖析 — 最小堆實現、入隊出隊、建堆全過程圖解

Java 集合深度系列（五）：PriorityQueue 源碼級剖析 — 最小堆實現、入隊出隊、建堆全過程圖解

PriorityQueue 是 Java 集合框架中基於最小堆實現的無界優先隊列。不同於普通隊列的 FIFO，它保證每次出隊（poll/peek）獲得隊列中最小元素（按自然順序或自定義 Comparator）。本文從數據結構原理、源碼核心方法、動態圖解、性能複雜度、使用陷阱五個維度徹底講透。

一、堆與優先隊列核心概念

1. 堆的兩大性質

• 堆有序性：任意節點值 ≤（最小堆）或 ≥（最大堆）其父節點值。根節點始終是全局最小/最大值。
• 完全二叉樹：除最後一層外每層滿，最後一層靠左排列。無空洞，利於數組緊湊存儲。

2. 數組映射完全二叉樹的數學規律

對於 0-based 索引數組 queue[]，節點 i 的：

• 左子節點：left(i) = 2*i + 1
• 右子節點：right(i) = 2*i + 2
• 父節點：parent(i) = (i-1) >>> 1 (無符號右移 1 位，等價除 2 取整)
• 最後一個非葉子節點索引：(size >>> 1) - 1

這種映射讓樹形結構在數組中無指針開銷、緩存友好、隨機訪問 O(1)。

二、建堆：heapify() 自下而上沉底

源碼 private void heapify()：

for (int i = (size >>> 1) - 1; i >= 0; i--)
    siftDown(i, (E) queue[i]);

• 從最後一個非葉子節點開始，依次向前對每個節點執行 siftDown（下沉）。
• 葉子節點無需處理，天然滿足堆性質。
• 時間複雜度 O(n)（非直觀的 O(n log n)，證明基於樹高加權求和）。

動態演示：元素 {6,5,3,1,4,8,7} 建最小堆過程

三、核心源碼深度解析

1. 入隊：offer() → siftUp() 上浮

public boolean offer(E e) {
    if (e == null) throw new NullPointerException();
    modCount++;
    int i = size;
    if (i >= queue.length) grow(i + 1); // 擴容 1.5倍 + 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 siftUpComparable(int k, E x) {
    Comparable key = (Comparable) 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; // 最終位置放入
}

入隊圖解：插入 2 到堆 [1,3,5,4,6]

2. 出隊：poll() → removeAt(0) → siftDown() 下沉

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

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 key = (Comparable) 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) 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;
}

出隊圖解：根節點移除，尾元素下沉

3. 任意位置移除：removeAt(i) — 雙向調整

private E removeAt(int i) {
    // ... 邊界檢查 ...
    int s = --size;
    if (s == i) queue[i] = null; // 刪除尾部，直接置 null
    else {
        E moved = (E) queue[s];
        queue[s] = null;
        siftDown(i, moved); // 先嘗試下沉
        if (queue[i] == moved) { // 位置未變，說明需上浮
            siftUp(i, moved);
        }
    }
    return null;
}

• 先下沉後上浮，保證堆性質恢復。兩者互斥，只會執行一個。
• 上浮場景：移除的節點原本就很小，尾元素較大，下沉無動作，需上浮找到正確位置。

四、時間複雜度總結表

五、關鍵特性與避坑指南

1. 非線程安全：多線程環境用 PriorityBlockingQueue（內部用 ReentrantLock + Condition）。
2. 不允許 null 元素：offer(null) 拋 NPE，因比較器無法處理 null。
3. 迭代器無序：iterator() 返回數組順序遍歷，不保證優先級順序。需有序輸出請 Arrays.sort(queue.toArray()) 或反複 poll()。
4. 無容量上限：動態擴容 grow()，大量數據預估初始容量避免頻繁擴容拷貝。
5. 自定義 Comparator：構造函數傳入 Comparator，覆蓋自然順序，注意處理 null 與一致性。
6. 序列化：實現 Serializable，寫入 size、comparator、queue 數組內容。

六、實戰應用場景

• Top K 問題：維持大小 K 的最小堆，遍歷數據流，O(n log k) 獲取前 K 大。
• 任務調度：按優先級/執行時間排序的定時任務隊列（如 ScheduledThreadPoolExecutor 內部使用 DelayedWorkQueue 繼承自 PriorityQueue）。
• Dijkstra / A* 最短路徑：優先展開距離最小節點。
• 合併 K 個有序鏈表/數組：堆維護 K 個指針當前最小值。

七、總結

PriorityQueue 以數組存儲完全二叉樹、siftUp/siftDown 維護最小堆性質，實現了O(log n) 入隊出隊、O(1) 取最小的高性能優先隊列。掌握其建堆 O(n) 線性算法、雙向調整移除邏輯、非線程安全與迭代器無序等核心細節，是面試高頻考點與高併發任務調度系統設計的基石。下一期我們將剖析 ArrayDeque 雙端隊列與 LinkedList 的異同，敬請期待！