1. 項(xiàng)目概述為什么優(yōu)先級(jí)隊(duì)列是Java開(kāi)發(fā)者的必備內(nèi)功在Java的世界里數(shù)據(jù)結(jié)構(gòu)是構(gòu)建一切復(fù)雜邏輯的基石。當(dāng)你處理需要按特定順序消費(fèi)元素的場(chǎng)景時(shí)比如任務(wù)調(diào)度、數(shù)據(jù)流合并或者實(shí)現(xiàn)像迪杰斯特拉這樣的圖算法一個(gè)簡(jiǎn)單的ArrayList或LinkedList往往力不從心。這時(shí)優(yōu)先級(jí)隊(duì)列Priority Queue及其背后的核心實(shí)現(xiàn)——堆Heap就成為了你工具箱里不可或缺的利器。簡(jiǎn)單來(lái)說(shuō)優(yōu)先級(jí)隊(duì)列是一種特殊的隊(duì)列它不遵循“先進(jìn)先出”的原則而是讓每個(gè)元素都攜帶一個(gè)“優(yōu)先級(jí)”出隊(duì)時(shí)總是優(yōu)先級(jí)最高或最低的元素先出去。在Java中java.util.PriorityQueue類就是它的標(biāo)準(zhǔn)實(shí)現(xiàn)。而“堆”則是實(shí)現(xiàn)這種高效出隊(duì)操作的數(shù)據(jù)結(jié)構(gòu)它是一種特殊的完全二叉樹(shù)。對(duì)于開(kāi)發(fā)者尤其是面臨面試或處理性能敏感場(chǎng)景時(shí)理解堆不僅僅是為了回答“Java八股文”更是為了在遇到“OutOfMemoryError: Java heap space”時(shí)能精準(zhǔn)定位或者在優(yōu)化算法時(shí)知道如何選擇正確的數(shù)據(jù)結(jié)構(gòu)。我見(jiàn)過(guò)不少項(xiàng)目因?yàn)殄e(cuò)誤地使用了普通列表進(jìn)行頻繁的排序和取極值操作導(dǎo)致性能瓶頸。而一個(gè)恰當(dāng)?shù)腜riorityQueue往往能將時(shí)間復(fù)雜度從O(n log n)降至O(log n)。接下來(lái)我們就深入拆解這個(gè)既基礎(chǔ)又強(qiáng)大的數(shù)據(jù)結(jié)構(gòu)。2. 核心原理堆是如何讓優(yōu)先級(jí)隊(duì)列如此高效的要理解優(yōu)先級(jí)隊(duì)列必須先吃透堆。堆不是那種讓你“頭大”的復(fù)雜概念它其實(shí)是一個(gè)非常直觀且高效的結(jié)構(gòu)。2.1 堆的本質(zhì)與兩種形態(tài)堆在邏輯上是一棵完全二叉樹(shù)這意味著除了最后一層其他層都是滿的并且最后一層的節(jié)點(diǎn)都盡可能靠左排列。這個(gè)特性使得我們可以用一個(gè)簡(jiǎn)單的數(shù)組來(lái)存儲(chǔ)堆從而省去了指針的開(kāi)銷這也是它高效的原因之一。對(duì)于數(shù)組中下標(biāo)為i的節(jié)點(diǎn)假設(shè)從0開(kāi)始索引其父節(jié)點(diǎn)的下標(biāo)為(i - 1) / 2向下取整。其左子節(jié)點(diǎn)的下標(biāo)為2 * i 1。其右子節(jié)點(diǎn)的下標(biāo)為2 * i 2。堆的關(guān)鍵特性在于堆序性這決定了元素的順序大頂堆Max-Heap任何一個(gè)父節(jié)點(diǎn)的值都大于或等于其子節(jié)點(diǎn)的值。因此堆頂根節(jié)點(diǎn)即數(shù)組的第一個(gè)元素存儲(chǔ)的是整個(gè)堆中的最大值。小頂堆Min-Heap任何一個(gè)父節(jié)點(diǎn)的值都小于或等于其子節(jié)點(diǎn)的值。因此堆頂存儲(chǔ)的是整個(gè)堆中的最小值。Java的PriorityQueue默認(rèn)就是一個(gè)小頂堆。你可以通過(guò)傳入自定義的Comparator來(lái)輕松構(gòu)建一個(gè)大頂堆。2.2 核心操作上浮與下沉堆的所有魔法都圍繞兩個(gè)基礎(chǔ)操作展開(kāi)上浮Sift Up / Swim和下沉Sift Down / Heapify。上浮Sift Up當(dāng)一個(gè)新元素被插入到堆的末尾數(shù)組尾部時(shí)它可能會(huì)破壞堆序性。上浮操作就是不斷將這個(gè)新節(jié)點(diǎn)與其父節(jié)點(diǎn)比較對(duì)于小頂堆如果它比父節(jié)點(diǎn)小如果順序不對(duì)就交換它們的位置直到堆序性恢復(fù)或到達(dá)根節(jié)點(diǎn)。這個(gè)過(guò)程是元素從底部“冒”上來(lái)的過(guò)程。// 上浮操作的偽代碼邏輯小頂堆 private void siftUp(int k) { while (k 0) { int parent (k - 1) 1; // 無(wú)符號(hào)右移一位等價(jià)于 (k-1)/2 if (queue[k].compareTo(queue[parent]) 0) break; // 當(dāng)前節(jié)點(diǎn)已大于等于父節(jié)點(diǎn)滿足堆性質(zhì)停止 swap(k, parent); // 否則交換當(dāng)前節(jié)點(diǎn)和父節(jié)點(diǎn) k parent; // 繼續(xù)向上檢查 } }下沉Sift Down當(dāng)我們需要取出堆頂元素即優(yōu)先級(jí)最高的元素后通常會(huì)將堆的最后一個(gè)元素移到堆頂。這個(gè)“臨時(shí)頂替”的元素幾乎肯定會(huì)破壞堆序性。下沉操作就是將它與其子節(jié)點(diǎn)中較小對(duì)于小頂堆的那個(gè)比較如果比子節(jié)點(diǎn)大就交換位置并繼續(xù)向下比較和交換直到恢復(fù)堆序性或到達(dá)葉子節(jié)點(diǎn)。// 下沉操作的偽代碼邏輯小頂堆 private void siftDown(int k) { int half size 1; // 只需檢查非葉子節(jié)點(diǎn) while (k half) { int child (k 1) 1; // 左孩子索引 int right child 1; // 右孩子索引 // 找出左右孩子中較小的那個(gè) if (right size queue[right].compareTo(queue[child]) 0) child right; if (queue[k].compareTo(queue[child]) 0) break; // 當(dāng)前節(jié)點(diǎn)已小于等于最小子節(jié)點(diǎn)滿足堆性質(zhì)停止 swap(k, child); // 否則交換當(dāng)前節(jié)點(diǎn)和較小子節(jié)點(diǎn) k child; // 繼續(xù)向下檢查 } }注意PriorityQueue的remove(Object o)和contains(Object o)方法的時(shí)間復(fù)雜度是O(n)因?yàn)樗鼈冃枰闅v數(shù)組。如果你需要頻繁地按值刪除或檢查存在性PriorityQueue可能不是最佳選擇需要考慮TreeSet等結(jié)構(gòu)。2.3 時(shí)間復(fù)雜度分析基于這兩個(gè)操作優(yōu)先級(jí)隊(duì)列的核心API效率極高插入offer(E e)將新元素放至數(shù)組末尾然后執(zhí)行一次上浮。上浮的路徑最長(zhǎng)等于樹(shù)的高度。對(duì)于有n個(gè)元素的完全二叉樹(shù)其高度約為log?n。因此插入操作的時(shí)間復(fù)雜度為O(log n)。查看堆頂peek()直接返回?cái)?shù)組下標(biāo)為0的元素時(shí)間復(fù)雜度為O(1)。取出堆頂poll()將堆頂元素下標(biāo)0取出將末尾元素移至堆頂然后對(duì)新的堆頂執(zhí)行一次下沉。下沉的路徑最長(zhǎng)也等于樹(shù)的高度。因此取出操作的時(shí)間復(fù)雜度也為O(log n)。這種效率對(duì)比起每次操作都需要全排序的簡(jiǎn)單列表優(yōu)勢(shì)是壓倒性的。3. 從零構(gòu)建手寫(xiě)一個(gè)簡(jiǎn)易優(yōu)先級(jí)隊(duì)列理解了原理最好的鞏固方式就是動(dòng)手實(shí)現(xiàn)一個(gè)。我們來(lái)實(shí)現(xiàn)一個(gè)基于小頂堆的簡(jiǎn)易版MyPriorityQueue支持泛型和自定義比較器。3.1 類結(jié)構(gòu)與初始化我們使用一個(gè)ArrayList作為底層存儲(chǔ)因?yàn)樗葦?shù)組更便于動(dòng)態(tài)擴(kuò)容。import java.util.ArrayList; import java.util.Comparator; import java.util.NoSuchElementException; public class MyPriorityQueueT { private ArrayListT heap; private Comparator? super T comparator; // 默認(rèn)構(gòu)造使用元素的自然順序要求T實(shí)現(xiàn)Comparable public MyPriorityQueue() { this.heap new ArrayList(); this.comparator null; } // 使用自定義比較器構(gòu)造 public MyPriorityQueue(Comparator? super T comparator) { this.heap new ArrayList(); this.comparator comparator; } // 內(nèi)部比較方法優(yōu)先使用自定義比較器否則使用自然順序 SuppressWarnings(unchecked) private int compare(T a, T b) { if (comparator ! null) { return comparator.compare(a, b); } else { return ((Comparable? super T) a).compareTo(b); } } }3.2 實(shí)現(xiàn)核心輔助方法上浮與下沉接下來(lái)實(shí)現(xiàn)我們之前討論的上浮和下沉操作。// 上浮操作 private void siftUp(int k) { while (k 0) { int parent (k - 1) / 2; // 計(jì)算父節(jié)點(diǎn)索引 if (compare(heap.get(k), heap.get(parent)) 0) { break; // 當(dāng)前節(jié)點(diǎn)值 父節(jié)點(diǎn)值滿足小頂堆性質(zhì)停止 } swap(k, parent); // 否則交換 k parent; // 繼續(xù)向上檢查 } } // 下沉操作 private void siftDown(int k) { int size heap.size(); int half size / 2; // 第一個(gè)葉子節(jié)點(diǎn)的索引 while (k half) { int child 2 * k 1; // 左孩子索引 int right child 1; // 右孩子索引 // 找出左右孩子中較小的那個(gè) if (right size compare(heap.get(right), heap.get(child)) 0) { child right; } if (compare(heap.get(k), heap.get(child)) 0) { break; // 當(dāng)前節(jié)點(diǎn)值 較小子節(jié)點(diǎn)值滿足性質(zhì)停止 } swap(k, child); // 否則交換 k child; // 繼續(xù)向下檢查 } } // 交換元素 private void swap(int i, int j) { T temp heap.get(i); heap.set(i, heap.get(j)); heap.set(j, temp); }3.3 實(shí)現(xiàn)對(duì)外API基于上浮和下沉實(shí)現(xiàn)主要的隊(duì)列操作就水到渠成了。// 插入元素 public boolean offer(T e) { if (e null) throw new NullPointerException(); // 仿照J(rèn)DK不支持null heap.add(e); // 添加到末尾 siftUp(heap.size() - 1); // 對(duì)末尾元素進(jìn)行上浮 return true; } // 查看堆頂元素不移除 public T peek() { return heap.isEmpty() ? null : heap.get(0); } // 取出堆頂元素 public T poll() { if (heap.isEmpty()) { return null; } int size heap.size(); T result heap.get(0); // 堆頂元素 T last heap.remove(size - 1); // 移除末尾元素 if (!heap.isEmpty()) { heap.set(0, last); // 將末尾元素放到堆頂 siftDown(0); // 對(duì)新的堆頂進(jìn)行下沉 } return result; } // 獲取隊(duì)列大小 public int size() { return heap.size(); } // 判斷隊(duì)列是否為空 public boolean isEmpty() { return heap.isEmpty(); }實(shí)操心得在poll()方法中先取出末尾元素再移除remove的技巧是為了避免在heap.set(0, last)時(shí)如果堆只有一個(gè)元素last就是被移除的堆頂本身導(dǎo)致錯(cuò)誤。這種邊界條件的處理是手寫(xiě)數(shù)據(jù)結(jié)構(gòu)時(shí)最容易出錯(cuò)的地方。3.4 測(cè)試我們的手寫(xiě)隊(duì)列寫(xiě)個(gè)簡(jiǎn)單的測(cè)試用例驗(yàn)證功能是否正確。public class TestMyPriorityQueue { public static void main(String[] args) { // 測(cè)試小頂堆默認(rèn) MyPriorityQueueInteger minHeap new MyPriorityQueue(); minHeap.offer(5); minHeap.offer(1); minHeap.offer(3); minHeap.offer(2); System.out.println(小頂堆出隊(duì)順序:); while (!minHeap.isEmpty()) { System.out.print(minHeap.poll() ); // 應(yīng)輸出 1 2 3 5 } System.out.println(); // 測(cè)試大頂堆通過(guò)自定義比較器 MyPriorityQueueInteger maxHeap new MyPriorityQueue((a, b) - b - a); maxHeap.offer(5); maxHeap.offer(1); maxHeap.offer(3); maxHeap.offer(2); System.out.println(大頂堆出隊(duì)順序:); while (!maxHeap.isEmpty()) { System.out.print(maxHeap.poll() ); // 應(yīng)輸出 5 3 2 1 } } }通過(guò)這個(gè)手寫(xiě)過(guò)程你會(huì)對(duì)PriorityQueue內(nèi)部offer和poll時(shí)數(shù)組元素的移動(dòng)、堆序性的維護(hù)有肌肉記憶般的理解。這遠(yuǎn)比死記硬背面試題答案要扎實(shí)得多。4. 實(shí)戰(zhàn)應(yīng)用場(chǎng)景與經(jīng)典問(wèn)題剖析懂了原理也實(shí)現(xiàn)了基礎(chǔ)版本現(xiàn)在來(lái)看看PriorityQueue在哪些真實(shí)場(chǎng)景中大放異彩。這能幫你未來(lái)在設(shè)計(jì)中快速聯(lián)想到這個(gè)工具。4.1 場(chǎng)景一合并K個(gè)有序鏈表力扣第23題這是面試中的超高頻題目。你有K個(gè)升序鏈表需要將它們合并成一個(gè)新的升序鏈表。暴力方法是把所有節(jié)點(diǎn)扔進(jìn)數(shù)組再排序時(shí)間復(fù)雜度O(N log N)其中N是總節(jié)點(diǎn)數(shù)。更優(yōu)的方法是使用小頂堆。思路初始化一個(gè)容量為K的小頂堆PriorityQueue并定義比較器為比較節(jié)點(diǎn)的值。將K個(gè)鏈表的頭節(jié)點(diǎn)全部放入堆中。循環(huán)從堆中彈出最小節(jié)點(diǎn)接到結(jié)果鏈表后面。如果被彈出的節(jié)點(diǎn)還有下一個(gè)節(jié)點(diǎn)則將下一個(gè)節(jié)點(diǎn)放入堆中。重復(fù)步驟3-4直到堆為空。代碼實(shí)現(xiàn)public ListNode mergeKLists(ListNode[] lists) { if (lists null || lists.length 0) return null; // 創(chuàng)建小頂堆比較鏈表節(jié)點(diǎn)的值 PriorityQueueListNode heap new PriorityQueue(lists.length, (a, b) - a.val - b.val); // 虛擬頭節(jié)點(diǎn)簡(jiǎn)化邊界處理 ListNode dummy new ListNode(-1); ListNode cur dummy; // 將所有鏈表的頭節(jié)點(diǎn)入堆非空才入 for (ListNode node : lists) { if (node ! null) { heap.offer(node); } } while (!heap.isEmpty()) { ListNode minNode heap.poll(); // 取出當(dāng)前最小節(jié)點(diǎn) cur.next minNode; cur cur.next; // 如果該節(jié)點(diǎn)還有后繼將后繼節(jié)點(diǎn)入堆 if (minNode.next ! null) { heap.offer(minNode.next); } } return dummy.next; }復(fù)雜度分析每個(gè)節(jié)點(diǎn)都會(huì)入堆和出堆一次。堆的大小最大為K。因此每次插入和刪除是O(log K)。總共有N個(gè)節(jié)點(diǎn)總時(shí)間復(fù)雜度為O(N log K)遠(yuǎn)優(yōu)于O(N log N)?？臻g復(fù)雜度為O(K)用于存儲(chǔ)堆。4.2 場(chǎng)景二數(shù)據(jù)流中的中位數(shù)力扣第295題要求設(shè)計(jì)一個(gè)數(shù)據(jù)結(jié)構(gòu)能高效地支持向其中添加數(shù)字并能快速找出所有數(shù)字的中位數(shù)。中位數(shù)定義如果數(shù)據(jù)個(gè)數(shù)是奇數(shù)中位數(shù)是排序后中間的數(shù)如果是偶數(shù)則是中間兩個(gè)數(shù)的平均值。思路維護(hù)兩個(gè)堆一個(gè)大頂堆maxHeap存儲(chǔ)較小的一半數(shù)字一個(gè)小頂堆minHeap存儲(chǔ)較大的一半數(shù)字。并約定當(dāng)總數(shù)為偶數(shù)時(shí)兩個(gè)堆大小相等中位數(shù)是兩個(gè)堆頂?shù)钠骄?。?dāng)總數(shù)為奇數(shù)時(shí)讓maxHeap比minHeap多一個(gè)元素中位數(shù)是maxHeap的堆頂。維護(hù)平衡每次插入后確保maxHeap的堆頂 minHeap的堆頂并且兩個(gè)堆的大小差不超過(guò)1。代碼實(shí)現(xiàn)class MedianFinder { private PriorityQueueInteger maxHeap; // 存儲(chǔ)較小一半大頂堆 private PriorityQueueInteger minHeap; // 存儲(chǔ)較大一半小頂堆 public MedianFinder() { maxHeap new PriorityQueue((a, b) - b - a); // 通過(guò)比較器實(shí)現(xiàn)大頂堆 minHeap new PriorityQueue(); } public void addNum(int num) { // 先加入maxHeap maxHeap.offer(num); // 保證maxHeap的堆頂 minHeap的堆頂 if (!minHeap.isEmpty() maxHeap.peek() minHeap.peek()) { minHeap.offer(maxHeap.poll()); } // 維護(hù)兩個(gè)堆的大小平衡 if (maxHeap.size() minHeap.size() 1) { minHeap.offer(maxHeap.poll()); } else if (minHeap.size() maxHeap.size()) { maxHeap.offer(minHeap.poll()); } } public double findMedian() { if (maxHeap.size() minHeap.size()) { return maxHeap.peek(); } else { return (maxHeap.peek() minHeap.peek()) / 2.0; } } }這個(gè)設(shè)計(jì)使得添加數(shù)字的時(shí)間復(fù)雜度為O(log N)查找中位數(shù)的時(shí)間復(fù)雜度為O(1)非常高效。4.3 場(chǎng)景三任務(wù)調(diào)度系統(tǒng)在后臺(tái)開(kāi)發(fā)中經(jīng)常需要處理帶有優(yōu)先級(jí)的任務(wù)。例如一個(gè)訂單處理系統(tǒng)VIP用戶的訂單需要優(yōu)先處理或者一個(gè)定時(shí)任務(wù)系統(tǒng)需要根據(jù)任務(wù)的執(zhí)行時(shí)間優(yōu)先級(jí)來(lái)調(diào)度。模擬實(shí)現(xiàn)class Task implements ComparableTask { String id; int priority; // 優(yōu)先級(jí)數(shù)值越小優(yōu)先級(jí)越高如1-緊急5-普通 String content; public Task(String id, int priority, String content) { this.id id; this.priority priority; this.content content; } Override public int compareTo(Task other) { return Integer.compare(this.priority, other.priority); // 小頂堆優(yōu)先級(jí)數(shù)值小的先出 } Override public String toString() { return String.format(Task[%s, priority%d]: %s, id, priority, content); } } public class TaskScheduler { private PriorityQueueTask taskQueue; public TaskScheduler() { taskQueue new PriorityQueue(); } public void submitTask(Task task) { taskQueue.offer(task); System.out.println(已提交: task); } public Task processNextTask() { Task task taskQueue.poll(); if (task ! null) { System.out.println(正在處理: task); } else { System.out.println(任務(wù)隊(duì)列為空。); } return task; } public static void main(String[] args) { TaskScheduler scheduler new TaskScheduler(); scheduler.submitTask(new Task(T1, 5, 處理普通報(bào)表)); scheduler.submitTask(new Task(T2, 1, 緊急告警響應(yīng))); // 優(yōu)先級(jí)最高 scheduler.submitTask(new Task(T3, 3, 用戶重要請(qǐng)求)); scheduler.processNextTask(); // 應(yīng)處理T2 scheduler.processNextTask(); // 應(yīng)處理T3 scheduler.processNextTask(); // 應(yīng)處理T1 } }通過(guò)這個(gè)例子可以看到PriorityQueue讓任務(wù)調(diào)度器的實(shí)現(xiàn)變得異常簡(jiǎn)潔和高效。5. 高級(jí)話題、性能調(diào)優(yōu)與避坑指南在實(shí)際生產(chǎn)環(huán)境中使用PriorityQueue還有一些進(jìn)階知識(shí)和坑需要注意。5.1 堆排序原地排序的優(yōu)雅實(shí)現(xiàn)堆排序是堆數(shù)據(jù)結(jié)構(gòu)的一個(gè)直接應(yīng)用它是一種原地的、時(shí)間復(fù)雜度為O(n log n)的不穩(wěn)定排序算法。其過(guò)程分為兩步建堆Heapify將無(wú)序數(shù)組調(diào)整成一個(gè)堆?？梢詮淖詈笠粋€(gè)非葉子節(jié)點(diǎn)開(kāi)始向前依次對(duì)每個(gè)節(jié)點(diǎn)執(zhí)行下沉操作。這個(gè)過(guò)程的時(shí)間復(fù)雜度是O(n)而不是O(n log n)這是一個(gè)有趣的數(shù)學(xué)結(jié)論。排序?qū)⒍秧斣刈畲蠡蜃钚∨c當(dāng)前堆的末尾元素交換然后堆的大小減一并對(duì)新的堆頂元素執(zhí)行下沉操作以恢復(fù)堆序性。重復(fù)此過(guò)程直到堆中只剩一個(gè)元素。public class HeapSort { public void sort(int[] arr) { int n arr.length; // 1. 建堆大頂堆 for (int i n / 2 - 1; i 0; i--) { siftDown(arr, n, i); } // 2. 排序 for (int i n - 1; i 0; i--) { // 將堆頂元素最大值與末尾交換 swap(arr, 0, i); // 對(duì)剩余元素重新建堆下沉堆頂 siftDown(arr, i, 0); } } private void siftDown(int[] arr, int n, int i) { int largest i; int left 2 * i 1; int right 2 * i 2; if (left n arr[left] arr[largest]) largest left; if (right n arr[right] arr[largest]) largest right; if (largest ! i) { swap(arr, i, largest); siftDown(arr, n, largest); } } private void swap(int[] arr, int i, int j) { int temp arr[i]; arr[i] arr[j]; arr[j] temp; } }5.2PriorityQueue的擴(kuò)容與迭代順序擴(kuò)容機(jī)制PriorityQueue底層使用Object[]數(shù)組存儲(chǔ)。當(dāng)元素?cái)?shù)量超過(guò)數(shù)組容量時(shí)會(huì)自動(dòng)擴(kuò)容。JDK中的策略是如果當(dāng)前容量小于64則擴(kuò)容為原來(lái)的2倍2否則擴(kuò)容為原來(lái)的1.5倍。這和ArrayList的擴(kuò)容邏輯類似。頻繁插入大量數(shù)據(jù)時(shí)預(yù)初始化一個(gè)合適的大小通過(guò)構(gòu)造函數(shù)PriorityQueue(int initialCapacity)可以避免多次擴(kuò)容帶來(lái)的性能損耗和數(shù)組拷貝。迭代無(wú)序非常重要PriorityQueue的迭代器iterator()和forEach遍歷不保證以任何特定的順序遍歷元素。如果你需要按優(yōu)先級(jí)順序遍歷必須使用poll()方法依次取出元素。這是因?yàn)槎阎槐ＷC了堆頂元素的順序內(nèi)部數(shù)組的存儲(chǔ)順序并不代表優(yōu)先級(jí)順序。PriorityQueueInteger pq new PriorityQueue(); pq.offer(3); pq.offer(1); pq.offer(2); System.out.println(錯(cuò)誤遍歷順序不確定:); for (Integer num : pq) { // 可能是 [1, 3, 2] 或其他 System.out.print(num ); } System.out.println(\n正確遍歷按優(yōu)先級(jí):); while (!pq.isEmpty()) { System.out.print(pq.poll() ); // 保證輸出 1 2 3 }5.3 常見(jiàn)問(wèn)題排查與性能調(diào)優(yōu)ClassCastException當(dāng)隊(duì)列中的元素沒(méi)有實(shí)現(xiàn)Comparable接口并且也沒(méi)有在構(gòu)造時(shí)提供Comparator嘗試插入元素就會(huì)拋出此異常。務(wù)必確保元素可比較。OutOfMemoryError: Java heap space這不是數(shù)據(jù)結(jié)構(gòu)本身的錯(cuò)誤而是JVM堆內(nèi)存不足。如果PriorityQueue中存儲(chǔ)了大量對(duì)象例如緩存了大量任務(wù)可能導(dǎo)致此錯(cuò)誤。需要分析內(nèi)存使用考慮是否需要對(duì)隊(duì)列大小設(shè)限或者使用更節(jié)省內(nèi)存的數(shù)據(jù)結(jié)構(gòu)。并發(fā)修改異常PriorityQueue不是線程安全的。在多線程環(huán)境下一個(gè)線程在迭代另一個(gè)線程在修改隊(duì)列會(huì)拋出ConcurrentModificationException。需要使用線程安全的替代品如PriorityBlockingQueue。性能瓶頸在極端情況下如果堆的高度變得很大例如元素?cái)?shù)量極多每次offer和poll的O(log n)操作也可能成為瓶頸。對(duì)于固定大小的Top-K問(wèn)題例如始終只維護(hù)最大的100個(gè)數(shù)可以設(shè)置堆的固定大小當(dāng)堆滿后新元素與堆頂比較決定是否替換并下沉這樣可以將復(fù)雜度控制在O(log K)其中K是固定大小。自定義對(duì)象排序?yàn)樽远x類實(shí)現(xiàn)Comparable接口或提供Comparator時(shí)要確保比較邏輯與equals方法保持一致雖然不是強(qiáng)制要求但最佳實(shí)踐如此并且滿足自反性、對(duì)稱性和傳遞性否則在依賴排序的集合中可能導(dǎo)致不可預(yù)知的行為。5.4PriorityQueuevsTreeSet兩者都能提供有序的元素訪問(wèn)但有著本質(zhì)區(qū)別特性PriorityQueueTreeSet核心接口QueueSet(同時(shí)實(shí)現(xiàn)SortedSet)允許重復(fù)元素是否有序遍歷僅能通過(guò)poll()按序取出迭代器無(wú)序迭代器按元素順序遍歷中序遍歷基礎(chǔ)操作時(shí)間復(fù)雜度offer/poll: O(log n)add/remove/contains: O(log n)按值刪除remove(Object o): O(n)remove(Object o): O(log n)線程安全版本PriorityBlockingQueueConcurrentSkipListSet選擇依據(jù)如果需要存儲(chǔ)可重復(fù)元素并按優(yōu)先級(jí)處理選PriorityQueue。如果需要一個(gè)不重復(fù)的有序集合并能快速按值查找或刪除選TreeSet。6. 源碼淺析與設(shè)計(jì)模式窺探最后我們簡(jiǎn)單看看JDK中PriorityQueue的源碼片段理解其工業(yè)級(jí)實(shí)現(xiàn)細(xì)節(jié)并看看其中蘊(yùn)含的設(shè)計(jì)思想。1. 底層存儲(chǔ)與關(guān)鍵字段public class PriorityQueueE extends AbstractQueueE implements java.io.Serializable { // 存儲(chǔ)元素的數(shù)組 transient Object[] queue; // 元素?cái)?shù)量 private int size 0; // 比較器如果為null則使用自然排序 private final Comparator? super E comparator; // 修改次數(shù)用于迭代器的快速失敗機(jī)制 transient int modCount 0; // ... 其他代碼 }可以看到核心就是一個(gè)對(duì)象數(shù)組加一個(gè)比較器。transient關(guān)鍵字修飾的字段不會(huì)被序列化。2. 擴(kuò)容方法grow(int minCapacity)private void grow(int minCapacity) { int oldCapacity queue.length; // 容量小于64時(shí)翻倍否則增長(zhǎng)50% int newCapacity oldCapacity ((oldCapacity 64) ? (oldCapacity 2) : (oldCapacity 1)); // 處理溢出和最大容量限制 if (newCapacity - MAX_ARRAY_SIZE 0) newCapacity hugeCapacity(minCapacity); queue Arrays.copyOf(queue, newCapacity); }這就是前面提到的擴(kuò)容策略是一種空間換時(shí)間的權(quán)衡。3. 核心方法siftUp和siftDown JDK的實(shí)現(xiàn)和我們手寫(xiě)的邏輯一致但使用了更優(yōu)化的位運(yùn)算如 1代替/2進(jìn)行無(wú)符號(hào)右移并且對(duì)于可比較和不可比較的情況做了區(qū)分siftUpComparable和siftUpUsingComparator體現(xiàn)了代碼的嚴(yán)謹(jǐn)性。4. 設(shè)計(jì)模式——模板方法模式PriorityQueue的add、offer、remove等方法都定義在抽象類AbstractQueue中而PriorityQueue提供了具體的實(shí)現(xiàn)。同時(shí)它將核心的堆調(diào)整算法siftUp,siftDown封裝為私有方法對(duì)外提供穩(wěn)定的隊(duì)列操作接口。這種“將算法骨架定義在父類具體步驟延遲到子類”的思想是模板方法模式的體現(xiàn)保證了結(jié)構(gòu)穩(wěn)定且易于擴(kuò)展。理解這些源碼細(xì)節(jié)不僅能讓你在面試中游刃有余更能讓你在遇到復(fù)雜問(wèn)題時(shí)有能力去定制或優(yōu)化現(xiàn)有的工具。比如如果你需要實(shí)現(xiàn)一個(gè)支持快速按值刪除的優(yōu)先級(jí)隊(duì)列你可能需要額外維護(hù)一個(gè)HashMap來(lái)記錄元素在堆數(shù)組中的索引并在swap操作時(shí)更新這個(gè)映射。這已經(jīng)是Fibonacci Heap等更高級(jí)堆結(jié)構(gòu)的思路了。堆和優(yōu)先級(jí)隊(duì)列是數(shù)據(jù)結(jié)構(gòu)與算法領(lǐng)域的明珠它用簡(jiǎn)單的規(guī)則和巧妙的實(shí)現(xiàn)解決了高效的動(dòng)態(tài)極值查找問(wèn)題。從任務(wù)調(diào)度到算法優(yōu)化從理解JVM內(nèi)存模型注意此處的“堆”與數(shù)據(jù)結(jié)構(gòu)的“堆”是不同的概念到解決力扣難題它無(wú)處不在。掌握它不僅僅是掌握了一個(gè)工具類更是掌握了一種重要的算法思想。下次當(dāng)你需要處理“總是處理當(dāng)前最重要/最緊急的那個(gè)”這類問(wèn)題時(shí)不妨先想想這里是不是該用優(yōu)先級(jí)隊(duì)列了