源码:

Fibonacci heap

堆是一种很常见的完全二叉树,在这里我给大家普及一下Fibonacci heap。

注明:本文的图片来自于skywang12345。

认识时间复杂度

1
2
3
4
斐波那契堆:
MAKE_HEAP: O(1)
INSERT: O(1)
DELETE (DELETE-Key): O(log n)

认识其定义

斐波那契堆用来实现优先队列,其作用是跟二项堆和堆一样的。不同于堆的是斐波那契堆是一个可并堆,时间复杂度还要比二项堆和堆快那么一点。

不难看出,斐波那契堆是由很多个”堆”组成的,也就是一个森林。也不难发现,每一个”堆”不是完全二叉树,而且子节点的数量是2^n。

有一点要注意,成形的斐波那契堆不可以有子节点数量相同的两个堆。

认识存储结构

既然是一个森林,那么我们就不能用普通的方法来存储。这里我们用到双向链表等。先定义几个数组:

1
2
3
4
5
Key: 也就是值
Left-link: 左边的兄弟(这里的兄弟指的就是同一个父亲的儿子)
Right-link: 右边的兄弟
Son: 其中一个孩子的节点(我习惯于最左边的,这样子新的孩子来了就比较方便)(记录一个孩子,因为双向链表:所以知道所有孩子)
Father: 父亲

我们来看这幅图:

可以看出上下的链表和左右的链表,这就是它的存储方式。

INSERT

很简单,我们只要把众多的根中的min_place找出来,每一次插入,只要把值插入到min_place的左边或右边就可以了。(习惯性右边)

还有一种说法,可以把最右边的根的位置记录下来,这样子也是可以的。

DELETE

DELETE的真正意思就是取出最小值,完善堆,合并堆(前面说过了不能有两个子节点数量相同的堆,我们需要合并)。

下面这幅图把所有东西一起讲出来了:

我们也并不一定要搞两个堆来合并,可以一个堆。还要注意,插入的时候就不用合并了,我们等到DELETE的时候再合并。(合并后变成一个成形的斐波那契堆)

小结

1.不写出我的玄学代码pascal。(写不A)

2.时间复杂度真的会快!!!!!!(虽然O没有变)

3.可以参见skywang12345的博客。

4.Why is called Fibonacci heap?
自己讨论看看