用戶:Cutekibry/沙盒

配對堆是一種實現簡單、均攤複雜度優越的堆數據結構，由Michael Fredman、羅伯特·塞奇威克、Daniel Sleator、羅伯特·塔揚於1986年發明。 配對堆是一種多叉樹，並且可以被認為是一種簡化的斐波那契堆。對於實現例如普林姆最小生成樹算法等算法，配對堆是一個更優的選擇，且支持以下操作（假設該堆是最小堆）：

• 查找最小值：返回堆頂。
• 合併：比較兩個堆頂，將堆頂較大的堆設為另一個的孩子。
• 插入：創建一個只有一個元素的堆，並合併至原堆中。
• 減小元素（可選）：將以該節點為根的子樹移除，減小其權值，並合併回去。
• 刪除最小值：刪除根並將其子樹合併至一起。這裏有各種不同的方式。

配對堆時間複雜度的分析靈感來源於伸展樹。 其刪除最小值操作的時間複雜度為O(log n)，而查找最小值、合併和插入操作的均攤時間複雜度均為O(1)。

確定配對堆每次進行減小元素操作的均攤時間複雜度是困難的。最初，基於經驗，這個操作的時間複雜度被推測為是O(1)，但Fredman證明了對於某些操作序列，每次減小元素操作的時間複雜度至少為$\Omega (\log \log n)$。 在那之後，通過不同的均攤依據，Pettie證明了插入、合併及減小元素操作的均攤時間複雜度均為$O(2^{2{\sqrt {\log \log n}}})$，近似於$o(\log n)$。 Elmasry後來介紹了一種配對堆的變體，令其擁有所有斐波那契堆可以實現的操作，且減小元素操作的均攤時間複雜度為$O(\log \log n)$，但對於原始的數據結構，仍未知準確的$\Theta (\log \log n)$運行下限。此外，能否使刪除最小值在均攤時間複雜度為$o(\log n)$的同時，令插入操作的均攤時間複雜度為$O(1)$，目前也仍未得到解決。

儘管這比其他的，例如能實現均攤時間$O(1)$的減小元素的斐波那契堆，這樣的優先隊列算法更差，在實踐中配對堆的表現仍然很不錯。Stasko和Vitter， Moret和Shapiro， 以及Larkin、Sen和Tarjan 進行過配對堆和其他堆數據結構的實驗。 他們得出的結論是, 配對堆通常比基於數組的二叉堆和D叉堆的實際操作速度更快，而且在實踐中幾乎總是比其他基於指針的堆更快，其中包括諸如[[斐波納契堆]這樣的理論上更有效率的數據結構。

操作

刪除最小值

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