User:EtaoinWu/配对堆

配对堆是一种实现简单、均摊复杂度优越的堆数据结构，由Michael Fredman、罗伯特·塞奇威克、Daniel Sleator、羅伯特·塔揚于1986年发明。 配对堆是一种多叉树，并且可以被认为是一种简化的斐波那契堆。其可以用于实现例如普林姆最小生成树算法。

一个配对堆支持以下操作：

• 查找最小值：返回堆顶。
• 合并：比较两个堆顶，将堆顶较大的堆设为另一个的孩子。
• 插入：创建一个只有一个元素的堆，并合并至原堆中。
• 减小元素：将该结点所在子树移除，修改其权值，并合并回去。
• 删除最小值：删除根并将其子树合并至一起。这里有各种不同方式，决定了其复杂度。

配对堆的分析灵感来源于伸展树。 其删除最小值操作时间复杂度为O(log n)，其他操作均摊复杂度均为O(1) 。

操作

删除最小值

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