配對堆

配對堆
配對堆
類型	堆積
發明時間	1986年
發明者	邁克爾·弗雷德曼、羅伯特·塞奇威克、丹尼爾·斯萊托、羅伯特·塔揚
用大O符號表示的時間複雜度
算法
算法
插入
尋找最小值
刪除最小值
減小鍵值
合併

配對堆（英語：Pairing heap）是一種實現簡單、均攤複雜度優越的堆數據結構，由邁克爾·弗雷德曼、羅伯特·塞奇威克、丹尼爾·斯萊托、羅伯特·塔揚於1986年發明。^[1] 配對堆是一種多叉樹，並且可以被認為是一種簡化的斐波那契堆。對於實現例如普林姆最小生成樹算法等算法，配對堆是一個更優的選擇^[2]，且支持以下操作（假設該堆是最小堆）：

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

配對堆時間複雜度的分析靈感來源於伸展樹。^[1] 其delete-min操作的時間複雜度為 $O (log n)$ ，而find-min、merge和insert操作的均攤時間複雜度均為 $O (1)$ 。^[3]

確定配對堆每次進行decrease-key操作的均攤時間複雜度是困難的。最初，基於經驗，這個操作的時間複雜度被推測為是 $O (1)$ ，^[4]但弗雷德曼證明了對於某些操作序列，每次decrease-key操作的時間複雜度至少為 $\Omega (\log \log n)$ 。^[5] 在那之後，通過不同的均攤依據，Pettie證明了insert、merge及decrease-key操作的均攤時間複雜度均為 $O(2^{2{\sqrt {\log \log n}}})$ ，近似於 $o(\log n)$ 。^[6] Elmasry後來介紹了一種配對堆的變體，令其擁有所有斐波那契堆可以實現的操作，且decrease-key操作的均攤時間複雜度為 $O(\log \log n)$ ，^[7]但對於原始的數據結構，仍未知準確的 $\Theta (\log \log n)$ 運行下限。^[6]^[3]此外，能否使delete-min在均攤時間複雜度為 $o(\log n)$ 的同時，令insert操作的均攤時間複雜度為 $O(1)$ ，目前也仍未得到解決。^[8]

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

結構

一個配對堆要麼是一個空堆，要麼就是一個配對樹，由一個根元素與一個可能為空的配對樹列表所組成。堆的有序屬性使該列表中所有子樹的根元素都不小於該堆的根元素。下面描述了一個純粹的函數堆，我們假定它不支持decrease-key操作。

type PairingTree[Elem] = Heap(elem: Elem, subheaps: List[PairingTree[Elem]])
type PairingHeap[Elem] = Empty | PairingTree[Elem]

對於隨機存取機，一個基於指針的實現若要支持decrease-key操作，可以對每個節點使用三個指針做到，具體做法是用單向鍊表儲存節點的孩子：一個指針指向該節點的第一個孩子，一個指向它的下個兄弟，一個指向它的上個兄弟（對於最左邊的兄弟則指向它的父親）。或者，如果使用一個布爾標記表示「鍊表末尾」且令最後一個孩子指向它的父親，指向上個兄弟的指針也可以不使用。這在犧牲常數開銷的同時，令結構更加緊湊。^[1]

操作

find-min（查找最小值）

函數find-min簡單地返回該堆的堆頂：

function find-min(heap: PairingHeap[Elem]) -> Elem
  if heap is Empty
    error
  else
    return heap.elem

merge（合併）

合併一個空堆將會返回另一個堆，否則將會返回一個新堆，其將兩個堆的根元素中較小的元素當作新堆的根元素，並將較大的元素所在的堆合併到新堆的子堆中：

function merge(heap1, heap2: PairingHeap[Elem]) -> PairingHeap[Elem]
  if heap1 is Empty
    return heap2
  elsif heap2 is Empty
    return heap1
  elsif heap1.elem < heap2.elem
    return Heap(heap1.elem, heap2 :: heap1.subheaps)
  else
    return Heap(heap2.elem, heap1 :: heap2.subheaps)

insert（插入）

插入一個元素最簡單的方法是，將一個僅有該元素的新堆與需要被插入的堆合併：

function insert(elem: Elem, heap: PairingHeap[Elem]) -> PairingHeap[Elem]
  return merge(Heap(elem, []), heap)

delete-min（刪除最小值）

唯一比較複雜的操作即是堆中最小值的刪除操作。標準方法是：首先將子堆從左到右、一對一對地合併（這就是它叫這個名字的原因），然後再從右到左合併該堆。

function delete-min(heap: PairingHeap[Elem]) -> PairingHeap[Elem]
  if heap is Empty
    error
  else
    return merge-pairs(heap.subheaps)

這需要使用到輔助函數merge-pairs（合併對）：

function merge-pairs(list: List[PairingTree[Elem]]) -> PairingHeap[Elem]
  if length(list) == 0
    return Empty
  elsif length(list) == 1
    return list[0]
  else
    return merge(merge(list[0], list[1]), merge-pairs(list[2..]))

這確實實現了所描述的兩個通過從左向右、然後從右向左的合併策略。這可以下面的過程看到：

   merge-pairs([H1, H2, H3, H4, H5, H6, H7])
=> merge(merge(H1, H2), merge-pairs([H3, H4, H5, H6, H7]))
     # 合并H1和H2到H12，再处理列表中剩下的部分
=> merge(H12, merge(merge(H3, H4), merge-pairs([H5, H6, H7])))
     # 合并H3和H4到H34，再处理列表中剩下的部分
=> merge(H12, merge(H34, merge(merge(H5, H6), merge-pairs([H7]))))
     # 合并H5和H6到H56，再处理列表中剩下的部分
=> merge(H12, merge(H34, merge(H56, H7)))
     # 转换方向，合并最后两个堆，给出H567
=> merge(H12, merge(H34, H567))
     # 合并最后两个堆，给出H34567
=> merge(H12, H34567) 
     # 最终，合并第一个堆和剩下堆合并的结果
=> H1234567

運行時間統計

下面的時間複雜度中，^[10]O(f)是一個漸近的上界，而Θ(f)是一個準確的上界（見大O符號）。函數名均假設該堆為最小堆。

操作	二叉^[10]	左偏	二項^[10]	斐波那契^[10]^[11]	配對^[3]	Brodal^[12]^[a]
find-min	Θ(1)	Θ(1)	Θ(log n)	Θ(1)	Θ(1)	Θ(1)
delete-min	Θ(log n)	Θ(log n)	Θ(log n)	O(log n)^[b]	O(log n)^[b]	O(log n)
insert	O(log n)	Θ(log n)	Θ(1)^[b]	Θ(1)	Θ(1)	Θ(1)
decrease-key	Θ(log n)	Θ(n)	Θ(log n)	Θ(1)^[b]	o(log n)^[b]^[c]	Θ(1)
merge	Θ(n)	Θ(log n)	O(log n)^[d]	Θ(1)	Θ(1)	Θ(1)

^ Brodal和Okasaki後來描述了一個可持久化的變種，擁有同樣的運行上界，但不支持decrease-key。帶有n個元素的堆可以在O(n)時間內從下至上構建。^[13]
^ ^2.0 ^2.1 ^2.2 ^2.3 ^2.4 均攤時間。
^ 下界為 $\Omega (\log \log n)$ ，^[14]上界為 $O(2^{2{\sqrt {\log \log n}}})$ 。^[15]
^ n是較大堆的大小。

參考文獻

^ ^1.0 ^1.1 ^1.2 Fredman, Michael L.; Sedgewick, Robert; Sleator, Daniel D.; Tarjan, Robert E. The pairing heap: a new form of self-adjusting heap (PDF). Algorithmica. 1986, 1 (1): 111–129 [2018-04-13]. doi:10.1007/BF01840439. （原始內容存檔 (PDF)於2021-05-06）.
^ Mehlhorn, Kurt; Sanders, Peter. Algorithms and Data Structures: The Basic Toolbox (PDF). Springer. 2008: 231 [2018-04-13]. （原始內容存檔 (PDF)於2019-12-31）.
^ ^3.0 ^3.1 ^3.2 Iacono, John, Improved upper bounds for pairing heaps, Proc. 7th Scandinavian Workshop on Algorithm Theory (PDF), Lecture Notes in Computer Science 1851, Springer-Verlag: 63–77, 2000, ISBN 3-540-67690-2, arXiv:1110.4428 , doi:10.1007/3-540-44985-X_5
^ ^4.0 ^4.1 Stasko, John T.; Vitter, Jeffrey S., Pairing heaps: experiments and analysis (PDF), Communications of the ACM, 1987, 30 (3): 234–249 [2018-05-20], CiteSeerX 10.1.1.106.2988 , doi:10.1145/214748.214759, （原始內容存檔 (PDF)於2017-08-29）
^ Fredman, Michael L. On the efficiency of pairing heaps and related data structures (PDF). Journal of the ACM. 1999, 46 (4): 473–501. doi:10.1145/320211.320214. （原始內容 (PDF)存檔於2011年7月21日）.
^ ^6.0 ^6.1 Pettie, Seth, Towards a final analysis of pairing heaps (PDF), Proc. 46th Annual IEEE Symposium on Foundations of Computer Science: 174–183, 2005 [2018-05-20], ISBN 0-7695-2468-0, doi:10.1109/SFCS.2005.75, （原始內容存檔 (PDF)於2012-01-28）
^ Elmasry, Amr, Pairing heaps with $O(\log \log n)$ decrease cost (PDF), Proc. 20th Annual ACM-SIAM Symposium on Discrete Algorithms: 471–476, 2009 [2018-05-20], CiteSeerX 10.1.1.502.6706 , doi:10.1137/1.9781611973068.52, （原始內容存檔 (PDF)於2012-10-18）
^ ^8.0 ^8.1 Larkin, Daniel H.; Sen, Siddhartha; Tarjan, Robert E., A back-to-basics empirical study of priority queues, Proceedings of the 16th Workshop on Algorithm Engineering and Experiments (PDF): 61–72, 2014, CiteSeerX 10.1.1.638.5198 , arXiv:1403.0252 , doi:10.1137/1.9781611973198.7 ^{[永久失效連結]}
^ Moret, Bernard M. E.; Shapiro, Henry D., An empirical analysis of algorithms for constructing a minimum spanning tree, Proc. 2nd Workshop on Algorithms and Data Structures, Lecture Notes in Computer Science 519, Springer-Verlag: 400–411, 1991 [2018-05-20], CiteSeerX 10.1.1.53.5960 , ISBN 3-540-54343-0, doi:10.1007/BFb0028279, （原始內容存檔於2018-07-21）
^ ^10.0 ^10.1 ^10.2 ^10.3 Cormen, Thomas H. （英語：Thomas H. Cormen）; Leiserson, Charles E. （英語：Charles E. Leiserson）; Rivest, Ronald L. Introduction to Algorithms 1st. MIT Press and McGraw-Hill. 1990. ISBN 0-262-03141-8.
^ Fredman, Michael Lawrence; Tarjan, Robert E. Fibonacci heaps and their uses in improved network optimization algorithms (PDF). Journal of the Association for Computing Machinery. July 1987, 34 (3): 596–615. doi:10.1145/28869.28874.
^ Brodal, Gerth S., Worst-Case Efficient Priority Queues (PDF), Proc. 7th Annual ACM-SIAM Symposium on Discrete Algorithms: 52–58, 1996
^ Goodrich, Michael T.; Tamassia, Roberto. 7.3.6. Bottom-Up Heap Construction. Data Structures and Algorithms in Java 3rd. 2004: 338–341. ISBN 0-471-46983-1.
^ Fredman, Michael Lawrence. On the Efficiency of Pairing Heaps and Related Data Structures (PDF). Journal of the Association for Computing Machinery. July 1999, 46 (4): 473–501. doi:10.1145/320211.320214.
^ Pettie, Seth. Towards a Final Analysis of Pairing Heaps (PDF). FOCS '05 Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science: 174–183. 2005. CiteSeerX 10.1.1.549.471 . ISBN 0-7695-2468-0. doi:10.1109/SFCS.2005.75.

外部連結

Louis Wasserman discusses pairing heaps and their implementation in Haskell in The Monad Reader, Issue 16 （頁面存檔備份，存於互聯網檔案館） (pp. 37–52).
pairing heaps （頁面存檔備份，存於互聯網檔案館）, Sartaj Sahni

[brodal-14] Brodal和Okasaki後來描述了一個可持久化的變種，擁有同樣的運行上界，但不支持decrease-key。帶有n個元素的堆可以在O(n)時間內從下至上構建。^[13]

[amortized-15] 2.0 ^2.1 ^2.2 ^2.3 ^2.4 均攤時間。

[pairingdecreasekey-18] 下界為 $\Omega (\log \log n)$ ，^[14]上界為 $O(2^{2{\sqrt {\log \log n}}})$ 。^[15]

[merge-19] 是較大堆的大小。

[FSST-1] 1.0 ^1.1 ^1.2 Fredman, Michael L.; Sedgewick, Robert; Sleator, Daniel D.; Tarjan, Robert E. The pairing heap: a new form of self-adjusting heap (PDF). Algorithmica. 1986, 1 (1): 111–129 [2018-04-13]. doi:10.1007/BF01840439. （原始內容存檔 (PDF)於2021-05-06）.

[mehlhorn-2] Mehlhorn, Kurt; Sanders, Peter. Algorithms and Data Structures: The Basic Toolbox (PDF). Springer. 2008: 231 [2018-04-13]. （原始內容存檔 (PDF)於2019-12-31）.

[Iacono-3] 3.0 ^3.1 ^3.2 Iacono, John, Improved upper bounds for pairing heaps, Proc. 7th Scandinavian Workshop on Algorithm Theory (PDF), Lecture Notes in Computer Science 1851, Springer-Verlag: 63–77, 2000, ISBN 3-540-67690-2, arXiv:1110.4428 , doi:10.1007/3-540-44985-X_5

[StaskoVitter-4] 4.0 ^4.1 Stasko, John T.; Vitter, Jeffrey S., Pairing heaps: experiments and analysis (PDF), Communications of the ACM, 1987, 30 (3): 234–249 [2018-05-20], CiteSeerX 10.1.1.106.2988 , doi:10.1145/214748.214759, （原始內容存檔 (PDF)於2017-08-29）

[Fredman-5] Fredman, Michael L. On the efficiency of pairing heaps and related data structures (PDF). Journal of the ACM. 1999, 46 (4): 473–501. doi:10.1145/320211.320214. （原始內容 (PDF)存檔於2011年7月21日）.

[Pettie-6] 6.0 ^6.1 Pettie, Seth, Towards a final analysis of pairing heaps (PDF), Proc. 46th Annual IEEE Symposium on Foundations of Computer Science: 174–183, 2005 [2018-05-20], ISBN 0-7695-2468-0, doi:10.1109/SFCS.2005.75, （原始內容存檔 (PDF)於2012-01-28）

[Elmasry-7] Elmasry, Amr, Pairing heaps with $O(\log \log n)$ decrease cost (PDF), Proc. 20th Annual ACM-SIAM Symposium on Discrete Algorithms: 471–476, 2009 [2018-05-20], CiteSeerX 10.1.1.502.6706 , doi:10.1137/1.9781611973068.52, （原始內容存檔 (PDF)於2012-10-18）

[LST-8] 8.0 ^8.1 Larkin, Daniel H.; Sen, Siddhartha; Tarjan, Robert E., A back-to-basics empirical study of priority queues, Proceedings of the 16th Workshop on Algorithm Engineering and Experiments (PDF): 61–72, 2014, CiteSeerX 10.1.1.638.5198 , arXiv:1403.0252 , doi:10.1137/1.9781611973198.7 ^{[永久失效連結]}

[MoretShapiro-9] Moret, Bernard M. E.; Shapiro, Henry D., An empirical analysis of algorithms for constructing a minimum spanning tree, Proc. 2nd Workshop on Algorithms and Data Structures, Lecture Notes in Computer Science 519, Springer-Verlag: 400–411, 1991 [2018-05-20], CiteSeerX 10.1.1.53.5960 , ISBN 3-540-54343-0, doi:10.1007/BFb0028279, （原始內容存檔於2018-07-21）

[CLRS-10] 10.0 ^10.1 ^10.2 ^10.3 Cormen, Thomas H. （英語：Thomas H. Cormen）; Leiserson, Charles E. （英語：Charles E. Leiserson）; Rivest, Ronald L. Introduction to Algorithms 1st. MIT Press and McGraw-Hill. 1990. ISBN 0-262-03141-8.

[Fredman_And_Tarjan-11] Fredman, Michael Lawrence; Tarjan, Robert E. Fibonacci heaps and their uses in improved network optimization algorithms (PDF). Journal of the Association for Computing Machinery. July 1987, 34 (3): 596–615. doi:10.1145/28869.28874.

[12] Brodal, Gerth S., Worst-Case Efficient Priority Queues (PDF), Proc. 7th Annual ACM-SIAM Symposium on Discrete Algorithms: 52–58, 1996

[13] Goodrich, Michael T.; Tamassia, Roberto. 7.3.6. Bottom-Up Heap Construction. Data Structures and Algorithms in Java 3rd. 2004: 338–341. ISBN 0-471-46983-1.

[Fredman1999-16] Fredman, Michael Lawrence. On the Efficiency of Pairing Heaps and Related Data Structures (PDF). Journal of the Association for Computing Machinery. July 1999, 46 (4): 473–501. doi:10.1145/320211.320214.

[17] Pettie, Seth. Towards a Final Analysis of Pairing Heaps (PDF). FOCS '05 Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science: 174–183. 2005. CiteSeerX 10.1.1.549.471 . ISBN 0-7695-2468-0. doi:10.1109/SFCS.2005.75.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[a]

[b]

[c]

[d]

[13]

[14]

[15]

閱論編數據結構
類型	集合容器
抽象類型	關聯數組多重關連數組（英語：Multimap）串列前向串列堆疊隊列雙端隊列優先隊列雙端優先隊列集合多重集併查集可持久化數據結構線段樹
數組	字串位數組環形緩衝器動態數組哈希表哈希數組樹（英語：Hashed array tree）稀疏矩陣
鏈（英語：Linked data structure）	關聯表（英語：Association list）鍊表跳躍列表鬆散鍊表（英語：Unrolled linked list）異或鍊表
樹	線段樹自平衡二叉查找樹 B樹二叉樹 AA樹 AVL樹紅黑樹平衡樹伸展樹二叉查找樹堆二叉堆左偏樹二項堆斐波那契堆 R樹 R*樹 R+樹希爾伯特R樹（英語：Hilbert R-tree）希爾伯特前綴樹哈希樹
圖	有向圖有向無環圖二元決策圖無向圖確定性非循環有限自動機（英語：Deterministic acyclic finite state automaton）
數據結構術語列表

閱論編計算機科學中的樹
二叉樹	二元搜尋樹笛卡爾樹 MVP樹 Top tree（英語：Top tree） T樹線索二叉樹
自平衡二叉查找樹	AA樹 AVL樹左傾紅黑樹紅黑樹替罪羊樹伸展樹樹堆加權平衡樹
B樹	B+樹 B*樹 B^x樹 UB樹 2-3樹 2-3-4樹 (a,b)-樹（英語：(a,b)-tree）跳舞樹（英語：Dancing tree） H樹
堆	二叉堆二項堆斐波那契堆左偏樹配對堆斜堆范恩德蟒蛇樹（英語：Van Emde Boas tree）
Trie	後綴樹基數樹三叉查找樹 X-快速前綴樹 Y-快速前綴樹 AC自動機
二叉空間分割（BSP）樹	四叉樹八叉樹 k-d樹隱式k-d樹 VP樹
非二叉樹	指數樹（英語：Exponential tree）融合樹（英語：Fusion tree） PQ樹（英語：PQ tree） SPQR樹（英語：SPQR tree）
空間數據分割樹	R樹 R*樹 R+樹 X樹 M樹線段樹 (儲存區間) 線段樹 (區間查詢) 可持久化線段樹希爾伯特R樹優先R樹
其他樹	散列日曆散列樹手指樹（英語：Finger tree）順序統計樹度量樹（英語：Metric tree）覆蓋樹（英語：Cover tree） BK樹二重連鎖樹（英語：Doubly chained tree） iDistance（英語：iDistance） Link-cut tree（英語：Link-cut tree） Log-structured merge-tree（英語：Log-structured merge-tree）樹狀數組哈希樹