User: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叉堆的实际操作速度更快，而且在实践中几乎总是比其他基于指针的堆更快，其中包括诸如[[斐波纳契堆]这样的理论上更有效率的数据结构。

操作

删除最小值

配对堆达成其时间复杂度段关键在于将被删除的堆顶的孩子按次合并这一部分。最初的方式是将子树从左到右两两合并为原个数一半的树，再从右往左将所有新树合并到一起。