配对堆

配对堆
配对堆
类型	堆积
发明时间	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）树状数组哈希树