Java PriorityQueue 優先隊列源碼深度解析與實戰應用

Java PriorityQueue 優先隊列源碼深度解析與實戰應用

PriorityQueue (JDK 7) 基於二叉最小堆實現，隊頭始終為最小元素。無界、非線程安全、不允許 null、元素需實現 Comparable 或提供 Comparator。線程安全版本請用 PriorityBlockingQueue。

核心數據結構

• transient Object[] queue：堆數組
• int size：元素數量

關鍵算法

1. 建堆

• 從集合構造時：initElementsFromCollection 複製數據 → heapify() 自下而上 siftDown 調整為最小堆。

2. siftDown (下沉)

新增元素放入堆尾，或建堆時從非葉子節點開始，向下比較與子節點較小者交換，直到滿足堆性質或到達葉子。

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; // left child
        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;
}

3. siftUp (上浮)

入隊時新元素置於堆尾，向上與父節點比較，若更小則交換，直到根或父節點更小。

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

4. 動態擴容

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

小容量時 2倍+2 擴容，大容量時 1.5倍擴容。

實戰應用範例

例1：靜態數據流中求第 K 大元素

public boolean kthLargest(int data, int k, PriorityQueue<Integer> heap, int[] res) {
    if (heap.size() < k) {
        heap.offer(data);
        if (heap.size() == k) { res[0] = heap.peek(); return true; }
        return false;
    }
    if (heap.peek() < data) { heap.poll(); heap.offer(data); }
    res[0] = heap.peek(); return true;
}

維護大小為 K 的最小堆，堆頂即第 K 大。

例2：自定義對象帶 Comparator 入隊

class Customer { int id; String name; ... }
// 匿名 Comparator 按 id 排序
Comparator<Customer> idComparator = (c1, c2) -> c1.getId() - c2.getId();
Queue<Customer> pq = new PriorityQueue<>(7, idComparator);
// 入隊出隊自動按 id 升序

未提供 Comparator 且對象未實現 Comparable 會拋 ClassCastException。

輸出驗證

Processing Integer:9
Processing Integer:16
...
Processing Customer with ID=6
Processing Customer with ID=20
...

最小元素優先出隊，驗證最小堆特性。