斐波那契堆
结构描述
斐波那契堆是满足最小堆树的集合,最小堆树指的满足子节点key小于等于它父节点key,也就是说集合的最小key一定是所有树中某一个的root节点。斐波那契堆比二项堆更加灵活。树没有规定的形状,极端情况下一个单独的树可以包含堆所有的元素。这种灵活性允许以一种延迟的方式执行一些操作,将工作延迟到以后的操作中。例如:合并堆可以将两个树列表连接起来就可以简单的完成,降低key的操作有时从父节点中切出一个节点形成一个新树。
为了快速删除与合并,所有树的root节点使用双向链表环连接。每一个节点的子节点也使用同样的双向链表连接。为每一个树root节点我们维护一个它的子节点数量以及它是否被marked标记了。此外,我们还维护一个root节点的指针指向最小key节点。
斐波那契堆结构
- 有序堆树的集合
- 维护一个指针指向最小元素
- 一个标记集合记录被标记的节点
符号含义
- n = 堆的节点数
- rank(x) = 节点x的子节点数
- rank(H) = H堆的最大等级
- trees(H) = H堆树的数量
- marks(H) = H堆中被标记的节点数
势函数
插入
创建一个单独的树
添加至root链表;更新最小指针(如果需要的话)
插入分析
实际代价:O(1)
势的变化:+1
均摊代价:O(1)
删除最小
连接操作
使较大的root节点作为较小root节点的孩子节点
删除最小;合并它的子节点至root链表;更新最小
合并树保证没有任何两个root节点的等级相同
等级:root节点的孩子节点数量(不递归孩子节点的孩子节点,仅计算第一层孩子节点数)
由于节点23,节点17两个root节点的等级相同为0。将节点23连接至节点17
由于节点7,节点17两个root节点的等级相同为1。将节点17连接至节点7
由于节点7与节点24两个root节点的等级相同为2。将节点24连接至节点7
由于节点18,节点41等级相同为1。将节点41连接至节点18
删除最小分析
实际代价:O(rank(H) + trees(H))
- O(rank(H)) 合并最小的孩子节点至root链表复杂度
- O(rank(H)) + O(trees(H)) 更新最小指针复杂度
- O(rank(H)) + O(trees(H)) 合并树复杂度
势的变化:O(rank(H)) - trees(H)
- trees(H’ ) <= rank(H) + 1 直到没有两个树有一样的等级
- ΔΦ(H) <= rank(H) + 1 - trees(H).
分摊代价:O(rank(H))
Q&A
Q. 分摊代价O(rank(H))是否良好?
A. 如果只有插入与删除最小操作,那么是的
- 在所有树是二项树的情况下。(我们仅连接相同等级的树)
- 这意味着rank(H)<=logN
A. 是的,我们将要实现降低key,那么rank(H)=O(logN)
降低key
直观的为节点x降低key
- 果没有违反堆有序,直接降低节点x的key即可
- 否则,将节点x(包含子树)切出合并至root链表
- 保持树的单调性:一个节点的第二个子节点一旦切出,就将切下的节点合并至root链表(并且抹去它的标记unmark)
情景1:没有违反堆序
降低节点x的key(将节点x从46降低为29)
更新堆的最小指针(如果需要)
情景2a:违反了堆序
降低节点x的key(将节点x从29降低为15)
切出节点x子树,合并至root链表,抹除标记
如果节点x的父节点p处于unmarked状态(还没有丢失过子节点),mark标记它;
否则,切出节点p,合并至root链表,并且抹除它的标记unmark(并且递归所有的父节点,对丢失的是第二个子节点的节点做同样的处理)
情景2b:违反了堆序
降低节点x的key(将节点从35降低为5)
切出节点x(包含子树),合并至root链表,抹除标记
父节点已经丢失过一个子节点,切出节点p(包含子树),合并至root链表,抹除标记
递归父节点处理所有第二次丢失子节点的节点(节点24同样是第二次丢失子节点)
降低key分析
实际代价:O©
- O(1) 降低key更新key的复杂度
- O© 每次切出节点合并至root链表复杂度
势的变化:O(rank(H)) - trees(H)
- trees(H’) = trees(H) + c
- marks(H’) <= marks(H) - c + 2
- ΔΦ(H) <= c + 2 * (-c + 2) = 4-c
分摊代价:O(1)
合并
合并两个斐波那契堆
root链表是一个环,双向链表结构
合并分析
实际代价:O(1)
势的变化:O(0)
分摊代价:O(1)
删除
删除节点x
- 将节点x降低为极限小
- 对堆执行删除最小(上一步已经将要删除的节点降为极限小,所以完成这步即完成的节点x的删除)
删除分析
均摊代价:O(rank(H))
- O(1) 为降低key的均摊代价
- O(rank(H)) 删除最小的均摊代价
原文
https://www.cs.princeton.edu/~wayne/teaching/fibonacci-heap.pdf
https://en.wikipedia.org/wiki/Fibonacci_heap