斐波那契堆
提示
- 定义和特点:斐波那契堆是一种由最小堆或最大堆属性的树集合组成的数据结构,其中节点可以有多个子节点或没有子节点,操作效率高于二项式堆和二叉堆。
- 节点表示和结构:斐波那契堆的所有树的根节点通过循环双向链表相连,提高了访问速度,并使节点的删除和链表的连接仅需 O(1) 时间。
- 主要操作和复杂度:斐波那契堆支持插入(O(1))、查找最小值(O(1))、合并(O(1))、提取最小值(O(log n))、减小键值(O(1))和删除节点(O(log n))等操作。
Fibonacci 堆是一种数据结构,由遵循最小堆或最大堆属性的树的集合组成。我们已经在堆数据结构文章中讨论了最小堆和最大堆属性。这两个属性是 Fibonacci 堆上存在的树的特征。
在 Fibonacci 堆中,一个节点可以有多于两个孩子,或者根本没有孩子。此外,它比二项式堆和二叉堆支持更高效的堆操作。
Fibonacci 堆之所以被称 为Fibonacci堆,是因为这些树是以这样的方式构建的,即一个顺序为n
的树至少有Fn+2
个节点,其中Fn+2
是第(n + 2)
个斐波那契数。
Fibonacci 堆的属性
Fibonacci 堆的重要属性包括:
Fibonacci 堆中节点的内存表示
所有树的根节点都链接在一起,以便更快地访问。父节点的子节点通过一个循环双向链表连接在一起,如下所示。
使用循环双向链表有两个主要优点。
- 从树中删除节点需要
O(1)
的时间。 - 两个这样的链表的连接需要
O(1)
的时间。
Fibonacci 堆上的操作
插入
算法
insert(H, x)
degree[x] = 0
p[x] = NIL
child[x] = NIL
left[x] = x
right[x] = x
mark[x] = FALSE
将包含 x 的根列表与根列表 H 连接
如果 min[H] == NIL 或 key[x] < key[min[H]]
则 min[H] = x
n[H] = n[H] + 1
将节点插入到已存在的堆中,按照以下步骤进行。
- 为元素创建一个新节点。
- 检查堆是否为空。
- 如果堆为空,则将新节点设置为根节点并标记为
min
。 - 否则,将节点插入到根列表中并更新
min
。
查找最小值
最小元素始终由min
指针给出。
合并
两个 Fibonacci 堆的合并包括以下步骤。
- 连接两个堆的根。
- 通过选择新根列表中的最小键来更新
min
。