題幹與適用場景
請實作一個優先佇列，支援 add(task, priority)、update(task, priority)、remove(task) 和 pop()。相同優先級必須按加入順序返回；刪除和更新的攤銷複雜度應為 O(log n)，並說明如何處理堆中的失效項目。
這道題考察可變優先佇列的正確性，而不是只會呼叫一個 heap API。Python heapq 文件指出，優先佇列需要處理穩定排序、不可比較任務、優先級變化和待刪除元素；常見做法是用計數器解決平局，用字典定位項目，再用惰性刪除維護堆不變量。
面試官考察點
第一項是能否寫出堆元素的完整排序鍵：優先級、加入序號和任務。第二項是更新與刪除時不會直接破壞堆結構。第三項是能否處理重複任務、空佇列、已刪除堆頂和長期垃圾項目。
回答前需要釐清的問題
- 優先級是數字還是可比較物件？ 預設是可比較的整數，數值越小越優先。
- 任務 ID 是否唯一？ 預設唯一；重複
add視為更新或明確報錯。 - 是否需要穩定順序？ 預設相同優先級按首次加入順序返回。
- 是否允許惰性刪除暫時佔用記憶體？ 允許短期佔用，但要說明清理和重建策略。
- 是否並行呼叫？ 預設單執行緒；並行版本需要外部鎖或執行緒安全容器。
30 秒回答框架
「我用最小堆保存 [priority, sequence, task]，用字典把任務 ID 映射到目前有效項目。更新先把舊項目标記為 removed，再插入帶新序號的新項目；刪除同樣只標記失效。pop 時持續彈出失效項目，直到找到目前項目。序號保證同優先級穩定，字典保證定位 O(1)，堆操作是 O(log n)，惰性項目透過週期性重建控制空間。」
分步驟深入解答
第一步：定義不變量和操作契約
堆頂必須是所有有效項目中最小的 (priority, sequence)。字典只保存每個任務目前的項目。一個任務最多有一個有效項目；舊項目可以暫時留在堆中，但不能再次返回。空佇列的 pop 返回明確錯誤或空值，面試時先說明選擇。
第二步：選擇可比較的堆元素
使用三元組 [priority, sequence, task]。sequence 來自單調計數器，保證兩個任務優先級相同仍可比較，同時不會比較任務物件本身。若優先級方向相反，可統一取負值或封裝比較器，但不要在不同操作中混用。
第三步：實作 add 和 update
首次 add 生成序號並寫入字典與堆。update 先檢查任務存在，把舊項目標記為 REMOVED，再插入新項目並覆蓋字典指標。這樣無需在堆陣列中搜尋或手動上浮、下沉，操作複雜度保持 O(log n)。
add(task, priority):
if task is active: mark old entry removed
entry = [priority, next(sequence), task]
current[task] = entry
heappush(heap, entry)第四步：實作 remove 和惰性刪除
remove 從字典刪除任務，並把對應堆項目的任務欄位替換為 REMOVED。直接從陣列刪除會破壞堆結構並需要額外調整。惰性刪除讓每次修改只觸碰一個已知項目，代價是垃圾項目會暫時存在。
第五步：實作 pop 的失效項目跳過
循環彈出堆頂；若任務標記為 REMOVED，繼續彈出；若字典中的項目不是目前彈出的同一物件，表示它已被更新，也跳過。找到有效項目後從字典刪除並返回任務。堆為空時再拋出空佇列錯誤。
第六步：證明複雜度和攤銷邊界
add、update 和 remove 各執行一次堆插入或標記，時間為 O(log n) 或 O(1) 標記。一次失效項目只會被 pop 彈出一次，因此所有跳過成本可以攤銷到產生該項目的更新或刪除上。若長期只更新不彈出，空間會增長，需要重建。
第七步：設計重建和空間控制
當堆長度超過有效項目的固定倍數，例如 2 倍，或失效項目超過閾值時，遍歷字典保留目前項目並重新建堆。重建是 O(n)，但低頻觸發後攤銷可控。若任務量有明確上限，也可在每次批次更新後清理，避免一次性停頓。
第八步：覆蓋邊界測試
至少測試空佇列、相同優先級穩定順序、重複更新、刪除後 pop、更新後舊項目到達堆頂、全部項目失效、不可比較任務物件和重建前後結果一致。用隨機操作與一個排序列表模型對拍，驗證每次 pop 的結果相同。
設計取捨與邊界
取捨一：惰性刪除還是索引堆
惰性刪除程式碼短、修改風險小，適合通用實作；索引堆可以立即刪除並控制空間，但需要維護位置映射，交換元素時容易出現 bug。若刪除比例極高且記憶體嚴格受限，再選擇索引堆。
取捨二：單調序號是否會溢位
固定寬度整數可能溢位，導致穩定順序錯誤。使用語言提供的無界整數，或在安全時機整體重新編號並重建堆。不要在有活動項目時簡單把計數器歸零。
取捨三：錯誤還是空值
函式庫通常對空佇列拋出明確例外，呼叫方可以區分「沒有任務」和「任務值為 null」。若產品介面偏好返回空值，必須在文件中固定語意，並保證任務本身允許的空值不會混淆。
失敗演練與演進計畫
演練一：連續更新同一任務
對一個任務連續更新 10,000 次，再 pop 並檢查只返回最新優先級一次。觀察失效項目數量，觸發重建後再次確認結果和堆不變量。
演練二：隨機混合操作
隨機產生 add、update、remove、pop，與簡單的字典加排序列表模型對拍。特別檢查相同優先級的序號順序和更新後舊項目不會洩漏。
演練三：例外和資源邊界
對不存在任務執行 update/remove，對空佇列執行 pop，並在達到記憶體閾值時觸發重建。驗證錯誤類型穩定、重建不會遺失任務，且重建期間不會暴露半成品狀態。
常見誤區與追問
誤區一：只存 priority 和 task
任務物件可能不可比較，同優先級時會觸發比較錯誤。必須加入穩定序號或不可比較包裝器。
誤區二：更新時直接修改堆內項目
修改後項目可能已經不在正確位置，堆不變量會被破壞。應惰性刪除舊項目並插入新項目。
誤區三：刪除時從陣列呼叫 remove
線性搜尋是 O(n)，隨後還要恢復堆結構。用字典定位並標記失效更簡單。
誤區四：pop 只檢查任務欄位
更新後的舊項目可能仍帶有同一個任務 ID。還要確認彈出的物件等於字典中的目前項目。
誤區五：忽略垃圾項目空間
惰性刪除不是免費記憶體。要設定重建閾值並監控堆長度、有效項目數和失效比例。
誤區六：沒有定義優先級方向
最小堆預設最小值優先。若業務說「數字越大越重要」，應在介面契約中明確轉換，避免 add 和 pop 使用相反規則。