配對堆

配對堆是一種堆資料結構，實現相對容易，並且具有極佳的實際平均效能。

配對堆是堆有序的多路樹結構，可以看作簡化的斐波那契堆。

它們被認為是實現諸如 Prim 最小生成樹演算法等演算法的“可靠選擇”，並支援以下操作（假設為最小堆）：

• 查詢最小值 (find-min) - 此函式負責返回堆的頂部元素。
• 合併 (meld) - 此函式負責比較兩個根元素，較小的元素保持為結果的根，較大的元素及其子樹作為此根的子節點新增。
• 插入 (insert) - 此函式負責為插入的元素建立一個新的堆，並將其合併到原始堆中。
• 減小鍵值 (decrease-key, 可選) - 此函式負責移除以要減小的鍵為根的子樹，用較小的鍵替換該鍵，然後將結果合併回堆中。
• 刪除最小值 (delete-min) - 此函式負責移除根節點，並對其子樹進行重複合併，直到只剩下一個樹。
• 每個節點都有一個指向左孩子的指標，左孩子指向該孩子的下一個兄弟節點。
• 配對堆示例如下：

配對堆的時間複雜度分析主要受到伸展樹的啟發。刪除最小值操作的平均時間複雜度被認為是 O(log n)，而查詢最小值、合併和插入操作的平均時間複雜度為 O(1)。

Arnab Chakraborty

更新於：2020年1月2日

692 次瀏覽

開啟您的職業生涯

完成課程獲得認證

開始學習