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