### PriorityQueue 的特性和原理 `PriorityQueue` 是基于堆（heap）實現的優先級隊列，通常是最小堆（即堆頂元素是最小值）。隊列中的元素按照自然順序或通過提供的比較器進行排序。 #### 主要特性 * **基于堆數據結構**：一般使用最小堆。 * **無界隊列**：可以動態擴容。 * **元素排序**：按照自然順序或通過自定義的比較器排序。 * **線程不安全**：不適用于多線程環境，需要手動同步。 ### PriorityQueue 的核心實現及源碼分析 #### 1\. 數據結構 `PriorityQueue` 的核心數據結構是一個動態數組，用于存儲堆中的元素。 ~~~ java復制代碼public class PriorityQueue<E> extends AbstractQueue<E> implements java.io.Serializable { private static final int DEFAULT_INITIAL_CAPACITY = 11; // 默認初始容量 transient Object[] queue; // 用于存儲元素的數組 private int size = 0; // 當前元素數量 private final Comparator<? super E> comparator; // 自定義比較器（可選） // 構造函數和其他方法省略... } ~~~ * `queue`: 動態數組，用于存儲堆中的元素。 * `size`: 當前隊列中的元素數量。 * `comparator`: 自定義的比較器（可選），用于定義元素的排序規則。 #### 2\. 插入元素 `offer` 方法用于插入元素，內部調用 `add` 方法。 ~~~ java復制代碼public boolean add(E e) { return offer(e); } 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 grow(int minCapacity) { int oldCapacity = queue.length; // 擴容策略：當容量小于 64 時，每次擴容為原來的兩倍；當容量大于等于 64 時，每次擴容為原來的 1.5 倍 int newCapacity = oldCapacity + (oldCapacity < 64 ? (oldCapacity + 2) : (oldCapacity >> 1)); if (newCapacity - Integer.MAX_VALUE > 0) newCapacity = hugeCapacity(minCapacity); queue = Arrays.copyOf(queue, newCapacity); // 擴容并復制元素到新數組 } private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) // 溢出 throw new OutOfMemoryError(); return (minCapacity > Integer.MAX_VALUE) ? Integer.MAX_VALUE : Integer.MAX_VALUE; } ~~~ * **空值檢查**：不允許插入 null 值。 * **擴容檢查**：如果當前數組已滿，則進行擴容。 * **插入元素**：將元素插入到數組末尾，然后通過 `siftUp` 方法進行堆調整。 `SiftUp` 方法： ~~~ java復制代碼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<? 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; // 插入元素放到正確位置 } ~~~ * **堆調整**：將新插入的元素與父節點進行比較，如果比父節點小，則交換位置，直到滿足堆的性質。 #### 3\. 獲取和移除元素 `poll` 方法用于獲取并移除隊列頭部元素： ~~~ java復制代碼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; // 返回堆頂元素 } ~~~ * **獲取堆頂元素**：返回并移除堆頂元素（數組第一個元素）。 * **堆調整**：將最后一個元素移到堆頂，然后通過 `siftDown` 方法進行堆調整。 `siftDown` 方法： ~~~ java復制代碼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<? 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; // 插入元素放到正確位置 } ~~~ * **堆調整**：將堆頂元素向下比較和交換，直到滿足堆的性質。 ### 總結 `PriorityQueue` 是一個基于堆數據結構實現的無界優先級隊列，提供高效的插入和刪除操作。其核心在于使用堆（最小堆或最大堆）來保持元素的順序，并通過 `siftUp` 和 `siftDown` 方法進行堆調整。 * **優點**： * 插入和刪除操作的時間復雜度為 O(log n)。 * 支持按優先級排序的元素訪問。 * **缺點**： * 線程不安全，需要在多線程環境中手動同步。 * 由于使用數組存儲元素，擴容可能會引起性能問題。 * **使用場景**： * 任務調度：根據任務的優先級進行調度。 * 數據流處理：需要按優先級處理數據的場景。