配对堆Pairing Heap

配对堆是一种可并堆,由Michael Fredman等人于1986年发明,具有简单实现和优越的均摊复杂度。本文介绍了配对堆的基本概念,包括FIND-MIN、MERGE、INSERT、DECREASE-KEY和DELETE-MIN等操作,并讨论了复杂度分析,指出在实践中配对堆通常比其他堆数据结构表现更好。

摘要生成于 C知道 ,由 DeepSeek-R1 满血版支持, 前往体验 >

前言

最近做一道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 ,我们用 S o n 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 的权值大于

评论
添加红包

请填写红包祝福语或标题

红包个数最小为10个

红包金额最低5元

当前余额3.43前往充值 >
需支付:10.00
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包
实付
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明:

1.余额是钱包充值的虚拟货币,按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载,可以购买VIP、付费专栏及课程。

余额充值