配对堆 配对堆英語Pairing heap是一种实现简单均摊复杂度优越的堆数据结构由邁克爾弗雷德曼罗伯特塞奇威克丹尼爾斯萊托羅伯特塔揚于年发明 配对堆是一种多叉树并且可以被认为是一种简化的斐波那契堆对于实现例如普林姆最小生成树算法等算法配对堆是一个更优的选择且支持以下操作假设该堆是最小堆 findmin查找最小值返回堆顶 merge合并比较两个堆顶将堆顶较大的堆设为另一个的孩子 insert插入创建一个只有一个元素的堆并合并至原堆中 decreasekey减小元素可选将以该节点为根的子树移除减小其权值并合并回去 deletemin删除最小值删除根并将其子树合并至一起这里有各种不同的方式 配对堆时间复杂度的分析灵感来源于伸展树 其deletemin操作的时间复杂度为Olog n而findminmerge和insert操作的均摊时间复杂度均为O 确定配对堆每次进行decreasekey操作的均摊时间复杂度是困难的最初基于经验这个操作的时间复杂度被推测为是O但弗雷德曼证明了对于某些操作序列每次decreasekey操作的时间复杂度至少为 Ω  log  log  n  displaystyle Omega log log n  在那之后通过不同的均摊依据Pettie证明了insertmerge及decreasekey操作的均摊时间复杂度均为 O    log  log  n  displaystyle Osqrt log log n 近似于 o  log  n  displaystyle olog n  Elmasry后来介绍了一种配对堆的变体令其拥有所有斐波那契堆可以实现的操作且decreasekey操作的均摊时间复杂度为 O  log  log  n  displaystyle Olog log n 但对于原始的数据结构仍未知准确的 Θ  log  log  n  displaystyle Theta log log n 运行下限此外能否使deletemin在均摊时间复杂度为 o  log  n  displaystyle olog n 的同时令insert操作的均摊时间复杂度为 O    displaystyle O 目前也仍未得到解决 尽管这比其他的例如能实现均摊时间 O    displaystyle O 的decreasekey的斐波那契堆这样的优先队列算法更差在实践中配对堆的表现仍然很不错Stasko和Vitter Moret和Shapiro 以及LarkinSen和Tarjan 进行过配对堆和其他堆数据结构的实验 他们得出的结论是 配对堆通常比基于数组的二叉堆和D叉堆的实际操作速度更快而且在实践中几乎总是比其他基于指针的堆更快其中包括诸如斐波纳契堆这样的理论上更有效率的数据结构