Heap 優先佇列 ·

介紹
#

Heap（優先佇列）可以在 O(log n) 內插入元素、取出最小值，而且隨時能用 O(1) 看到最小值。

辨識訊號：

要反覆取「目前最小 / 最大」的元素，而且集合會一直變動。
題目出現「第 k 大」、「最接近的 k 個」、「最早結束的」、「優先處理」。
要合併好幾條已經排好序的序列。

如果只需要取一次最小值，直接排序或 min() 就好，不需要 heap。

Python heapq 基本用法
#

import heapq

h = []
heapq.heappush(h, 3)          # O(log n)
smallest = h[0]               # O(1)，只看不取
smallest = heapq.heappop(h)   # O(log n)
heapq.heapify(arr)            # O(n)，原地轉成 heap

主要參數說明：
#

只有 min-heap：要 max-heap 就把值取負號，例如 heappush(h, -x)。
tuple 會依序比較每個欄位：(優先度, 次要條件, 資料)。第一個欄位相同時會比第二個，所以要放能比較的 tie-breaker，例如 index。
字串不能取負號：想要「分數高優先，分數相同時名字小優先」這種混合順序，可以自訂 class 的 __lt__（LC 2102）。

模板一：Top-K，維持大小為 k 的 heap
#

要「前 k 大」，就維持一個大小為 k 的 min-heap：堆頂是這 k 個裡面最小的，新元素比它大才換進來。

h = []
for x in nums:
    heapq.heappush(h, x)
    if len(h) > k:
        heapq.heappop(h)      # 丟掉 k 個裡最小的
# h[0] 就是第 k 大

時間 O(n log k)。

模板二：Lazy deletion（延遲刪除）
#

heapq 不支援刪除或修改中間的元素。做法是：修改時直接推一筆新資料進去，舊的留在 heap 裡；取出時再檢查堆頂是不是過期的。

current = {}                  # key -> 目前有效的值

def update(key, value):
    current[key] = value
    heapq.heappush(h, (-value, key))

def top():
    while h:
        neg_value, key = h[0]
        if current.get(key) == -neg_value:
            return key        # 有效
        heapq.heappop(h)      # 過期，丟掉
    return -1

主要參數說明：
#

驗證條件要能分辨「過期資料」：通常是比對 dict 裡目前的值（LC 3815、3885），或一個 online 陣列（LC 3607）。
每筆資料最多被推入、彈出各一次，均攤下來仍是 O(log n)。
heap 空了要回傳預設值，不然函式會回傳 None。

模板三：雙 heap
#

兩個 heap 分別管理兩種狀態，元素在兩邊移動：

空閒 / 忙碌（LC 2402 Meeting Rooms III）：空閒房間依編號排，忙碌房間依結束時間排。新會議開始前，先把已經結束的房間從「忙碌」移到「空閒」。
前 k 名 / 其他（LC 2102）：前 k 名用 min-heap，堆頂是第 k 名；其他用 max-heap，堆頂是第 k+1 名。
中位數（LC 295）：小的一半放 max-heap，大的一半放 min-heap。

模板四：K 路合併
#

合併 k 條已排序的序列，heap 裡只放每條序列目前的開頭：

h = [(lst[0], i, 0) for i, lst in enumerate(lists) if lst]
heapq.heapify(h)
while h:
    val, i, j = heapq.heappop(h)
    # 處理 val
    if j + 1 < len(lists[i]):
        heapq.heappush(h, (lists[i][j + 1], i, j + 1))

時間 O(N log k)。LC 632 在合併的同時記錄目前的最大值，LC 759 在合併的同時找空檔。

模板五：掃描線 + 結束時間 heap
#

依開始時間排序，heap 存「進行中的事件的結束時間」：

intervals.sort()
h = []
for start, end in intervals:
    while h and h[0] <= start:    # 半開區間 [start, end)：end == start 時可以重用
        heapq.heappop(h)
    heapq.heappush(h, end)
    best = max(best, len(h))      # LC 253：同時進行的最大數量