堆積 (Heap) 是一種特殊的完全二元樹,能在 O(1) 時間取得最大/最小值,O(log n) 時間插入和刪除。優先佇列 (Priority Queue) 基於堆積實作。
Notes:
- 看到「第 K 大/小」、「Top K」等關鍵字,優先考慮 Heap
- Kotlin/Java 中用 PriorityQueue 實作,預設為 Min Heap
- 兩個 Heap(一大一小)可以高效維護中位數
跨倉庫導讀#
- 對應理論章節:樹 ↗(堆/優先佇列)
#215
Kth Largest Element in an Array
#295
Find Median from Data Stream
#355
Design Twitter
#502
IPO
#621
Task Scheduler
#703
Kth Largest Element in a Stream
#767
Reorganize String
#973
K Closest Points to Origin
#1046
Last Stone Weight
#1094
Car Pooling
#1383
Maximum Performance of a Team
#1405
Longest Happy String
#1675
Minimize Deviation in Array
#1834
Single Threaded CPU
#1845
Seat Reservation Manager
#1882
Process Tasks Using Servers
#1985
Find the Kth Largest Integer in the Array
#2542
Maximum Subsequence Score