⛰️ Heap / Priority Queue

隨時取出最大/最小，Top-K 與排程。

19 題 · 1 篇導讀

📖 分類導讀

堆積 (Heap) 是一種特殊的完全二元樹，能在 O(1) 時間取得最大/最小值，O(log n) 時間插入和刪除。優先佇列 (Priority Queue) 基於堆積實作。

Notes:

看到「第 K 大/小」、「Top K」等關鍵字，優先考慮 Heap
Kotlin/Java 中用 PriorityQueue 實作，預設為 Min Heap
兩個 Heap（一大一小）可以高效維護中位數

Heap 與 Priority Queue

Min-heap / Max-heap：每個節點都不大於（或不小於）其子節點，所以根永遠是最小值（或最大值）。
Priority Queue 與 Heap 的關係：優先佇列是「每次取出優先級最高元素」的抽象；堆積是它最常見的實作。Kotlin/Java 的 PriorityQueue 預設 min-heap，要 max-heap 傳入 compareByDescending { it } 或反向比較器即可。

複雜度

操作	複雜度
取頂 (peek)	`O(1)`
插入 (offer)	`O(log n)`
取出頂 (poll)	`O(log n)`
從既有陣列建堆 (heapify)	`O(n)`

TIP

建堆是 O(n) 而非 O(n log n)——這是常被誤記的點。一次把整個陣列建成堆，比逐一插入 n 次更省。

常見套路

Top K：要前 k 大就維護大小為 k 的 min-heap，比堆頂大才換入，掃完堆裡就是前 k 大，O(n log k)。
資料流中位數：一個 max-heap 裝較小半邊、一個 min-heap 裝較大半邊，兩堆頂即可推出中位數。
多路合併：合併 k 條已排序串列時，用堆同時追蹤各路的當前最小元素。
Huffman 編碼：反覆從堆取出兩個最低頻節點合併，正是堆的經典應用。

NOTE

求「第 k 大」未必要堆。Quickselect（快速選擇）借快排的分割，平均 O(n) 就能找到第 k 大，代價是最壞 O(n^2) 且會打亂原陣列。資料量大且只問一次時，它常比堆更快。

本章深入

Heap 內部原理 (Heap Internals)：陣列表示法、siftUp/siftDown、heapsort 與建堆為何是 O(n)。

跨倉庫導讀

對應理論章節：樹（堆/優先佇列）

📘Heap Internals

#215Kth Largest Element in an ArrayMedium★★★★★⏱ O(n)#218The Skyline ProblemHard★★★★★⏱ O(n log n)#295Find Median from Data StreamHard★★★★★⏱ O(log n)#355Design TwitterMedium★★★★★⏱ O(k log k)#502IPOHard★★★★★⏱ O(n log n)#621Task SchedulerMedium★★★★★⏱ O(m * n)#703Kth Largest Element in a StreamEasy★★★★★⏱ O(log k)#767Reorganize StringMedium★★★★★⏱ O(n log 26)#973K Closest Points to OriginMedium★★★★★⏱ O(n log k)#1046Last Stone WeightEasy★★★★★⏱ O(n log n)#1094Car PoolingMedium★★★★★⏱ O(n log n)#1383Maximum Performance of a TeamHard★★★★★⏱ O(n log n)#1405Longest Happy StringMedium★★★★★⏱ O((a + b + c) * log 3)#1675Minimize Deviation in ArrayHard★★★★★⏱ O(n * log(maxVal) * log n)#1834Single Threaded CPUMedium★★★★★⏱ O(n log n)#1845Seat Reservation ManagerMedium★★★★★⏱ O(log n)#1882Process Tasks Using ServersMedium★★★★★⏱ O((n + m) log m)#1985Find the Kth Largest Integer in the ArrayMedium★★★★★⏱ O(n log k * L)#2542Maximum Subsequence ScoreMedium★★★★★⏱ O(n log n)