可合併雙端優先佇列 (Meldable DEPQs)

• 可合併雙端優先佇列 (MDEPQ) 定義為雙端優先佇列 (DEPQ)，除了上面列出的 DEPQ 操作外，還包括操作 meld(p, q) ... 將 DEPQ p 和 q 合併成單個 DEPQ。合併雙端優先佇列 p 和 q 的結果是一個包含 p 和 q 所有元素的單個雙端優先佇列。meld 操作是破壞性的，因為在合併之後，p 和 q 不會保留為獨立的 DEPQ。
• 為了在小於線性時間內合併兩個 DEPQ，必須使用顯式指標（而不是像堆的陣列表示那樣使用隱式指標）來表示 DEPQ，否則需要將線性數量的元素從初始位置移動到最終位置。
• 可以證明，當最小-最大對堆以這種方式表示時，一個大小為 n 的 DEPQ 可以與另一個大小為 k (其中 k<=n) 的 DEPQ 在 O(log(n/k)*log k) 時間內合併。
• 可以證明，合併大小分別為 a 和 b 的兩個最小-最大堆的複雜度為 Ω(a + b)。
• 一個 MDEPQ 實現允許計算最小和最大元素，插入元素，並在 O(1) 時間內合併兩個優先佇列。刪除最小或最大元素所需的時間為 O(log n)。
• 可以證明，左傾樹可以被改編以獲得 MDEPQ 的簡單表示，其中合併消耗對數時間，其餘操作具有與實現上述任何 DEPQ 表示時相同的漸近複雜度。
• 有趣的是，如果我們實現 FMPQ（快速可合併優先佇列）結構作為基礎 MPQ 結構，我們將獲得一個完全對應的 MDEPQ 結構，其中 removeMax 和 removeMin 消耗對數時間，其餘操作消耗常數時間。與雙優先佇列自適應相比，這種自適應非常優秀，因為空間需求幾乎減少了一半。此外，完全對應的自適應比雙優先佇列自適應更快。

Arnab Chakraborty

更新於：2020年1月3日

109 次瀏覽

啟動您的職業生涯

透過完成課程獲得認證

開始學習