使用者:EtaoinWu/配對堆

配對堆是一種實現簡單、均攤複雜度優越的堆數據結構，由Michael Fredman、羅伯特·塞奇威克、Daniel Sleator、羅伯特·塔揚於1986年發明。 配對堆是一種多叉樹，並且可以被認為是一種簡化的斐波那契堆。其可以用於實現例如普林姆最小生成樹算法。

一個配對堆支持以下操作：

• 查找最小值：返回堆頂。
• 合併：比較兩個堆頂，將堆頂較大的堆設為另一個的孩子。
• 插入：創建一個只有一個元素的堆，並合併至原堆中。
• 減小元素：將該結點所在子樹移除，修改其權值，並合併回去。
• 刪除最小值：刪除根並將其子樹合併至一起。這裡有各種不同方式，決定了其複雜度。

配對堆的分析靈感來源於伸展樹。 其刪除最小值操作時間複雜度為O(log n)，其他操作均攤複雜度均為O(1) 。

操作

刪除最小值

配對堆達成其時間複雜度段關鍵在於將被刪除的堆頂的孩子按次合併這一部分。最初的方式是將子樹從左到右兩兩合併為原個數一半的樹，再從右往左將所有新樹合併到一起。