JDK 源碼深度分析：PriorityQueue 堆實現全解析

一、結構概覽

PriorityQueue 基於最小堆實現：任意節點都是以它為根的子樹中最小元素。

• 邏輯結構：完全二叉樹
• 存儲結構：數組（隨機訪問快）
• 根節點（索引 0）為最小元素
• 索引關系：父節點 (i-1)/2，左子 2i+1，右子 2i+2

二、容量管理

初始容量

默認 11（DEFAULT_INITIAL_CAPACITY）

擴容策略

private void grow(int minCapacity) {
    int oldCapacity = queue.length;
    // 小數組翻倍+2，大數組增長 50%
    int newCapacity = oldCapacity + ((oldCapacity < 64) ? (oldCapacity + 2) : (oldCapacity >> 1));
    // 溢出保護
    if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity);
    queue = Arrays.copyOf(queue, newCapacity);
}

三、插入操作

調用 siftUpComparable（無比較器時）或 siftUpUsingComparator。

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;                            // 最終位置放入新元素
}

流程： 新元素放數組末尾 → 與父節點比較 → 若較小則父節點下移、索引上移 → 重複直到根或滿足性質 → 放入最終位置。

四、刪除操作

調用 siftDownComparable。

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

流程： 取出堆頂 → 末尾元素移至堆頂 → 與較小子節點比較 → 若較大則子節點上移、索引下移 → 重複直到葉或滿足性質 → 放入最終位置。

關鍵點： k < half 保證只處理非葉節點；child 初始為左子，有右子且更小則切換。

五、源碼地址

查看原文：https://blog.zswlib.com/2016/10/31/jdk%e6%ba%90%e7%a0%81%e5%88%86%e6%9e%90priorityqueue/