前言
最近做一道Dijkstra的题目,因为边数实在太大了( 109 10 9 ),用STL的priority_queue直接超时(事实上还会MLE)。有同学写配对堆的。刚好很久没学习新的数据结构了,就趁着这个机会补一补。
配对堆
配对堆 Pairing Heap 是一种实现简单、均摊复杂度优越的堆数据结构,由Michael Fredman、罗伯特·塞奇威克、Daniel Sleator、罗伯特·塔扬 于1986年发明。 配对堆是一种多叉树,并且可以被认为是一种简化的斐波那契堆。
(以上内容来自wikipedia)
怎么说呢?
首先,配对堆是一种可并堆,也支持与其他可并堆类似的操作,但是实现和原理较为简单(至少是相对与FIB堆)。
支持操作
配对堆主要支持以下操作:
- find-min(查找最小值):返回堆顶。
- merge(合并):比较两个堆顶,将堆顶较大的堆设为另一个的孩子。
- insert(插入):创建一个只有一个元素的堆,并合并至原堆中。
- decrease-key(减小元素)(可选):将以该节点为根的子树移除,减小其权值,并合并回去。
- delete-min(删除最小值):删除根并将其子树合并至一起。这里有各种不同的方式。
接下来我们一个一个详细地讲解这些操作。
说明
- 我们讲解时用小根堆作为例子(但示例图为大根堆,见谅)
- 对于每个节点 i i ,我们用 表示它的儿子节点的集合, Fai F a i 表示它的父亲节点。
- 一个堆的根我们设为 root r o o t
1 FIND-MIN
简单地返回该堆堆顶即可。
2 MERGE
首先合并空堆将返回另一个堆,否则我们返回新堆的根。
假设我们要把 Heap1 H e a p 1 和 Heap2 H e a p 2 这两个堆合并起来。
那么我们需要比较一下 rootHeap1 r o o t H e a p 1 和 rootHeap2 r o o t H e a p 2 的权值,不妨设 rootHeap1 r o o t H e a p 1 的权值大于