題幹與適用場景
你要為任務排程器實作可合併的最小優先佇列。呼叫方會頻繁合併兩個佇列，再插入工作並取出最小優先級。請實作 meld、insert、find-min 與 extract-min，說明隨機化、空堆、重複鍵與節點所有權。
隨機可合併堆以二元樹表達堆序，不維護左偏堆的秩等額外中繼資料。隨機選擇遞迴合併進入左子樹或右子樹，重點考察不變量、機率分析與可測試性。
面試官考察點
重點包括根鍵最小不變量、meld 的交換與結合語義、隨機數產生器邊界、重複鍵、節點歸屬、遞迴深度、銷毀策略，以及期望複雜度和最壞情況的區分。候選人也應能比較二元堆、左偏堆與配對堆的適用條件。
回答前需要釐清的問題
meld是否可以消耗輸入堆，還是必須保留兩個原堆？- 是否能注入隨機種子，以便重播失敗測試？
- 最大節點數與遞迴堆疊預算是多少？
- 是否需要穩定控制代號、任意刪除或
decrease-key？ - 目標是教學實作、工程吞吐量，還是需要嚴格最壞界？
30 秒回答框架
「每個節點保存鍵、值、左右子樹。meld(a,b) 先處理空樹，再讓較小根成為結果根；隨機決定把另一棵樹與左子樹或右子樹遞迴合併。insert 用單節點與根 meld，extract-min 用根的左右子樹 meld。如此根始終最小，操作通常為期望對數時間，但遞迴深度與隨機種子必須測試與限制。」
分步驟深入解答
第一步：定義節點和所有權
節點至少保存 key、value、left、right。堆物件保存根與節點數。若 meld 採用可變實作，輸入堆的根會被重新連接，介面必須明確輸入是否失效；若要求持久化，則需要路徑複製，複雜度和空間都會改變。
meld(a, b):
if a is empty: return b
if b is empty: return a
if b.key < a.key: swap(a, b)
if randomBit() == 0:
a.left = meld(a.left, b)
else:
a.right = meld(a.right, b)
return a第二步：維護 meld 不變量
先比較兩個根，較小鍵保留為根；相等鍵可以採固定平局規則或隨機規則，但不能破壞堆序。遞迴返回後，結果子樹的所有鍵仍不小於目前根，因此不變量沿路徑保持。
實作中要避免同一節點同時掛到兩個父節點下。可變 meld 應記錄輸入所有權，除錯版本可檢查節點計數和無環；持久化版本則不能直接重用會被修改的子樹。
第三步：實作 insert 與 find-min
insert 建立單節點樹並與目前根 meld，節點數加一。find-min 讀取根鍵；空堆依介面回傳空值或錯誤。重複鍵不應被去重，值相同也不代表節點相同。
若隨機源是全域狀態，測試難以重播。較穩妥的方式是把隨機源作為依賴注入，並在測試使用固定種子；生產環境仍要避免低品質或偏斜的隨機位實作。
第四步：實作 extract-min
取出根後，新根是原根左右子樹的 meld。先斷開舊根的兩個指標，再減少節點數；若堆擁有節點記憶體，最後釋放舊根。輸入堆被消耗時，舊根控制代號必須標記失效，避免再次參與合併。
若需要保留舊版本，就採持久化路徑複製，不能在共享節點上原地修改指標。這個選擇應在介面層寫清楚，否則呼叫方會遇到別名造成的隱蔽資料損壞。
第五步：說明複雜度邊界
隨機可合併堆的 meld、insert 和 extract-min 通常可給出期望對數時間或高機率對數時間的分析，具體表述取決於隨機模型與實作細節。find-min 是常數時間。空間為節點數的線性級別。
不要把期望界說成每次操作的最壞界；惡劣隨機序列可能形成較深樹。生產實作要限制遞迴風險，必要時改成顯式堆疊或設定深度監控，並用基準和隨機測試驗證分布。
第六步：測試與對照實作
把堆與標準優先佇列對拍，覆蓋空堆、重複鍵、交替 meld、連續 extract-min、固定隨機種子和極端深度。每次操作後檢查根最小、節點數正確、無環和所有權約束。
與配對堆相比，本題使用二元樹和隨機分支，不需要兄弟鏈表、兩遍合併或控制代號切斷；與左偏堆相比，不維護秩中繼資料，換取機率化分析。比較時要同時說明快取局部性、可變語義和證明要求。
高品質示範回答
我會把最小鍵留在根，meld 對空樹直接返回，非空時交換根使 a 較小，再隨機把 b 與 a.left 或 a.right 合併。insert 和 extract-min 都重用 meld，find-min 讀根。實作前確認 meld 是否消耗輸入；測試注入固定隨機源，對拍標準優先佇列，檢查無環、計數和根最小。複雜度表述為隨機模型下的期望或高機率對數時間，並單獨處理遞迴深度風險。
常見錯誤
- 隨機分支放在比較根之前 → 根可能不是最小鍵 → 先交換根，再隨機選擇子樹。
- 可變 meld 後繼續使用舊堆 → 節點同時擁有兩個父節點 → 明確消耗語義或實作持久化。
- 把期望界寫成最壞 O(log n) → 機率假設被遺漏 → 註明隨機模型和高機率邊界。
- 隨機源不可注入 → 失敗用例無法重播 → 依賴注入並固定種子測試。
- 遞迴沒有深度策略 → 極端樹可能耗盡呼叫堆疊 → 顯式堆疊、深度監控或文件化限制。
追問及應對
追問一：如何讓測試完全確定？
把隨機位產生器作為堆實例依賴，測試傳入固定序列或種子；生產再使用獨立實例，避免全域隨機狀態讓多個測試互相影響。
追問二：meld 必須保留輸入時怎麼辦？
採用持久化實作，對沿遞迴路徑的節點做路徑複製，未修改的子樹共享。需要同步更新空間複雜度和垃圾回收策略，不能繼續宣稱原地常數額外空間。
追問三：如何處理兩個堆都引用同一節點？
可變 API 應禁止跨堆共享並在除錯模式記錄歸屬；持久化 API 允許結構共享，但所有節點必須不可變。發現歸屬衝突時回傳錯誤，不要靜默修復。
追問四：為什麼不用配對堆？
配對堆適合需要 decrease-key 的場景，但要維護多叉子鏈和刪除後的重組；隨機可合併堆的二元 meld 更短，適合只需要合併、插入和取最小值且能接受機率化保證的介面。