优先队列——斐波那契堆

最近一直在写最短路径的迪杰斯特拉与双向迪杰斯特拉算法，使用优先队列可以极大的加快算法的运行效率。比如在ol数据集中，对于迪杰斯特拉算法用优先队列（二叉堆实现）代替普通的数组（数据结构书中提供的算法）快了将近60倍。

由上可得如何实现优先队列对迪杰斯特拉、双向迪杰斯特拉以及其它用到优先队列的最短路径求解算法（如reach、a*）等至关重要。另外对于一些其他用到优先队列的问题也具有相当的影响。

对于优先队列来说，只需要入队、出队即可，因为该文章只关注堆的插入（push）与删除（delete）操作，其它操作忽略。该文中出现的队列值越小优先级越高。

几种常见的实现优先队列的堆的时间复杂度比较如表1-1所示。

表1-1 常见堆的常见操作时间复杂度比较，其中n代表结点个数

操作

二叉堆

d叉堆

左式堆

二项堆

斐波那契堆

insert

o(log2n)

o(logdn)

o(1)

delete

o(d*logdn)

merge

o(n*log2n)

o(ndlogdn)

minimum

decrease-key

从理论上讲，当删除操作远远小于插入操作时，斐波那契堆是很理想的。但是，从实际上看，对于大多数应用来说，由于斐波那契堆的常数因子以及程序上设计的复杂性，使得它不如通常的二叉（或d叉）堆合适。因此斐波那契堆主要是理论上的意义。如果能设计出一种与斐波那契堆有相同的平摊时间界但又简单的数据结构，那么它就会有很大的使用价值。[1]

与二项堆一样，斐波那契堆是由一组最小堆有序树构成，但堆中的树并不一定是二项树。

3.1 基本数据结构

斐波那契堆中的结点包含keyvalue、child、leftbrother、rightbrother、parent、mark。其中，keyvalue为结点的数据值，mark用于标记该结点是否失去过孩子。因为斐波那契堆中允许降低指定结点的值，并将降低值的结点提升为根，而mark标记的存在可以保证斐波那契堆中的树不至于过深（自己理解，但是不理解即使很深的话影响哪些操作）。然而对于用斐波那契堆实现优先队列，mark与parent是不需要的，因此以下操作实现中不存在mark与parent域。

斐波那契堆的属性：minh，maxdegree，cons，keynum。其中minh指向当前堆中最小值（最高优先级）的结点，maxdegree记录了所有根结点的孩子个数的上界， cons用于辅助斐波那契堆的合并操作，keynum记录了当前对中结点个数。

另外我采用了模板类去实现该数据结构，这样为在不同环境下使用该优先队列（斐波那契堆实现）带来了方便。

3.2 插入

插入一个结点直接将该结点加到minh后边即可。参考代码第4节中push函数。

3.3 取值

对于优先队列只需取到最小值（优先级最大）即可，而属性minh即为结果。参考代码第4节中的top函数。

3.4 删除最小值

因为在插入的时并没有对堆进行任何的调整，才使得插入操作的代价为o(1)，而在删除时需要对堆进行合并操作，即将孩子个数（degree）相同的结点合并为一棵最小堆有序树。

具体操作步骤如下：

(1) 将minh的孩子提升为根；

(2) 删除minh所指向的结点，并将其后移一个位置；

(3) 用cons（类型：fibonacci**）辅助完成堆的合并，*(cons + i)指向孩子个数为i的结点；

(4) 顺序扫描根表，并将当前结点从根表移除（不是删除）到对应的*(cons+i)中（当前结点的孩子个数为i），若*(cons+i)处已有值则合并；反之扫描下一个根，直至根表为空；

(5) 将cons中的结点串联到根表中，并将minh指向当前最小根（最小值）结点。

该部分代码实现参考了，代码实现见第4节pop()。

注意：刚开始自己实现时用了cmap，即哈希，想着这样的查找代价与空间代价可以最低。用哈希辅助实现合并操作比参考[2]的实现插入删除100000个节点足足慢了一倍。小小郁闷一下。

分析：用cmap实现忽略了(1) 合并后节点个数不会太多，比如100000个节点只需17（? log2100000?）个空间；(2) 两个结点孩子均为i的结点合并得到一个有i+1个孩子的结点，不需要再去哈希。用[2]中的方法，即按照上述的计算过程实现后100000个结点的插入与删除操作时间由220ms降低为78ms。

4.1 编程环境

window 7 +vs2010

4.2 测试数据与测试结果

随机产生的100000个数据，首先根据二叉堆（biheap）[3]的结果验证该方法实现优先队列的正确性。其次比较了与[2]、[3]进行了时间比较，时间消耗如图4-1所示。

4-1 100000个插入、删除操作运行时间对比

结果剖析：network-fibonacci代表[2]中的代码，myself-fibonacci代表用斐波那契堆实现的优先队列，myself-biheap代表用二叉堆实现的优先队列，冒号后的数字表示运行时间。在二叉堆[3]的实现使用了静态数组，虽然插入时间复杂度高于斐波那契堆，但是因为其数组的操作简易性使得它的运行时间是最好的。另外统计表明二叉堆的插入操作平均为o(1)。

4.3 完整代码

参考文献

[1] 算法导论

[2]

[3]