題幹與適用場景
你需要為事件排程器實作可合併的最小優先佇列，任務優先級會動態降低。標準二元堆能完成基本操作，但 meld 和 decrease-key 需要額外成本。請實作配對堆，涵蓋節點句柄、連結、兩遍合併、刪除與邊界條件。
配對堆是 1986 年提出的自調整堆，目標是在實作簡單的同時獲得良好實務效能；原始論文只提供部分複雜度分析。題目考察候選人是否能區分程式正確性、攤銷分析和沒有證明的複雜度宣稱。
面試官考察點
重點包括最小堆不變量、常數時間 meld、兩遍 sibling pairing、句柄失效、decrease-key 的切斷與重新連結、空堆和重複鍵、記憶體管理，以及與二元堆和 Fibonacci 堆的取捨。
回答前需要釐清的問題
- 需要 decrease-key 還是只需要 push/pop，呼叫比例如何？
- 節點句柄是否必須穩定，刪除後如何偵測過期句柄？
- 是否允許遞迴，最大堆規模和堆疊預算是多少？
- 比較器是否可能拋出例外或改變，是否支援重複優先級？
- 目標是教學實作、低常數實務效能，還是有嚴格最壞複雜度證明？
30 秒回答框架
「每個節點保存 key、負載、父指標、最左子節點和下一個兄弟，並由句柄指向節點。link 比較兩個根，把較大根掛到較小根的子鏈表。delete-min 先摘除根，再從左到右兩兩 link，隨後從右到左合併。decrease-key 先切斷非根節點，再與根 meld。實作時維護句柄狀態，複雜度按攤銷和已知分析謹慎表述。」
分步驟深入解答
第一步：定義節點與句柄
節點保存鍵、負載、父節點、最左子節點和右兄弟。句柄直接指向節點，並帶有效標記或代數，防止刪除後繼續呼叫 decrease-key。根的父指標為空，兄弟鏈表末端也必須為空。
Node { key, value, parent, firstChild, nextSibling, alive }
Heap { root, size }比較器只負責排序，不應修改節點。重複鍵按穩定需求處理，不能把鍵相等誤當成節點相同。
第二步：實作 link 與 meld
link(a, b) 比較兩個根，令較大鍵的根成為較小鍵根的第一個子節點，並更新 parent 與 sibling 指標。meld 只需 link 兩個根；空堆直接返回另一個根。
每次指標變更後檢查根父指標為空、子節點 parent 指向目前節點和 size 不變。除錯建置可遍歷節點檢查無環，但生產路徑不應每次都線性驗證。
第三步：實作 insert 與 find-min
insert 建立單節點堆並與根 meld，返回穩定句柄。find-min 讀取根；空堆按介面約定返回空值或錯誤，不要解參照空指標。
如果呼叫方保存句柄，堆物件移動或擴容不能讓句柄失效，因此節點應獨立配置或透過穩定間接層管理。釋放策略必須明確由堆擁有節點還是由呼叫方管理負載。
第四步：實作 delete-min 的兩遍合併
刪除根後，把其子鏈表斷開為根列表。第一遍從左到右把相鄰根兩兩 link；若數量為奇數，最後一個根保留。第二遍從右到左依次 meld 結果。
deleteMin(h):
children = detachChildren(h.root)
pairs = linkAdjacent(children)
newRoot = mergeRightToLeft(pairs)
invalidate(h.root)
h.root = newRoot
h.size -= 1合併過程要清理舊 parent 和 sibling 指標，避免保留已刪除根的鏈路。根列表很長時用迭代實作，避免遞迴堆疊溢位。
第五步：實作 decrease-key
若新鍵不小於舊鍵，拒絕或採用獨立的 increase-key 方案。根節點只需更新鍵；非根節點先從父節點的子鏈表中切斷，修復 sibling 指標，再把該節點作為獨立根 meld。
切斷必須知道前驅兄弟，常見做法是掃描父節點的子鏈表，或增加 prevSibling 指標並承擔更多維護成本。句柄已失效、節點不屬於該堆或堆已銷毀時返回錯誤。
第六步：測試不變量與複雜度
隨機測試把配對堆與標準優先佇列對拍，涵蓋重複鍵、空堆、連續 decrease-key、刪除所有節點和隨機 meld。每輪驗證根是最小鍵、size 與存活節點一致、父子關係無環。
複雜度要區分已證明上界、攤銷直覺和實務測量。配對堆的 insert、meld 常數小，但 delete-min、decrease-key 的嚴格複雜度分析並非「所有操作都最壞 O(log n)」；面試中應明確假設並與二元堆、Fibonacci 堆比較。
高品質示範回答
我會用節點的 parent、firstChild、nextSibling 和穩定句柄實作 link、meld、兩遍 delete-min 與 decrease-key。decrease-key 對非根節點先從兄弟鏈切斷，再作為新根合併；delete-min 從左到右配對、從右到左合併。實作會對拍標準優先佇列並檢查無環和 size 不變量，同時謹慎區分攤銷分析、最壞界和實務效能。
常見錯誤
- 只改 key 不切斷節點 → 堆序和父子關係失效 → 非根 decrease-key 必須切斷再 meld。
- 兩遍合併方向寫反 → 堆形狀和結果錯誤 → 先左到右配對，再右到左合併。
- 句柄指向已刪除節點 → use-after-free 或跨堆操作 → 失效標記和歸屬校驗。
- 宣稱所有操作最壞 O(log n) → 複雜度結論無依據 → 區分攤銷、部分分析和測量。
- 遞迴處理長兄弟鏈 → 深度過大導致堆疊溢位 → 使用迭代串列。
追問及應對
追問一：為什麼不直接用二元堆？
二元堆陣列布局簡單、複雜度穩定；配對堆在 meld 和頻繁 decrease-key 場景可能有更小常數。應根據操作比例、記憶體區域性和證明要求選擇。
追問二：如何讓 decrease-key 不掃描兄弟鏈？
增加 prevSibling 指標或父節點的子集合索引，但每次 link 和切斷都要維護更多指標。空間和維護成本要與掃描成本比較。
追問三：如何支援刪除任意句柄？
把節點鍵降到負無窮後執行 decrease-key，再 delete-min；需要保證比較器和哨兵值安全，並正確失效句柄。
追問四：何時選擇 Fibonacci 堆？
當理論上的 decrease-key 攤銷界和演算法證明比實作複雜度更重要時考慮；工程程式碼還要評估快取區域性、記憶體開銷和實際基準。