Java上的数据结构Dijkstra：使用Fibonacci堆与PriorityQueue获得有趣的结果
最近，我使用两种数据结构对Dijkstra算法的运行时间进行了初步比较：基于Java的PriorityQueue（如果我没有弄错的话，基于二进制堆）和Fibonacci堆。我使用Java的currentTimeMillis（）进行计算。我得到的结果非常有趣。这是我的一个测试用例的输出：
Running Dijkstra's with 8 nodes and 27 links
- Execution time with binary heap: 1 miliseconds
- Execution time with Fibonacci heap: 4 miliseconds
诚然，我目前缺少数据集，上面的图表是我最大的（我计划很快制作更多）。但这有意义吗？我一直认为Fibonacci堆比其他数据结构更快，因为与其他数据结构相比，Fibonacci堆的摊销运行时间更长。我不确定这3毫秒的差异是从哪里来的。（如果有帮助的话，我正在Intel Core Ivy Bridge i7-3630M处理器上运行它。）
注意：我偶然发现了this thread，这可能解释了这个问题，尽管我仍然不清楚为什么斐波那契堆版本需要更长的时间。根据该线程，这可能是因为我的图不够密集，因此reduce Key操作的数量不足以让Fibonacci堆的性能真正发挥作用。这是唯一可能的结论，还是我还遗漏了什么
# 1 楼答案
Fibonacci堆比二进制堆（Java优先级队列中使用的数据结构）快渐近，因为Dijkstra的算法对于Fibonacci堆需要O（m+n logn）时间，而对于二进制堆则需要O（m logn）时间。这意味着对于大型密集图，在最坏的情况下，Fibonacci堆会更快
尽管Fibonacci堆比二进制堆渐进地快，但它们有着众所周知的大常数因子，而且Fibonacci堆上的许多基本操作需要很长时间才能完成。从长远来看，它们的性能将优于二进制堆，但对于小型图，常量项可能非常大，以至于斐波那契堆实际上速度较慢
其次，比较渐近运行时（O（m+nlogn）与O（mlogn））。如果您使用的图是稀疏的（即m=O（n）），那么这两个渐近运行时是相同的（O（n logn））。在这种情况下，斐波那契堆的理论优势并不存在，二进制堆可能是更好的选择
最后，请注意，big-O表示法指的是这种情况下的最坏情况行为，而不是平均情况。不久前有一篇论文表明，对于某种类型的随机图，Dijkstra的期望算法所需的时间远远低于最坏情况下的减少键和出列操作数。在这种情况下，即使在大型图上，二进制堆的性能也可能优于斐波那契堆，因为最坏情况下的行为不会被触发
希望这有帮助
# 2 楼答案
斐波那契堆具有更快的渐近性，但它们的常数因子并不一定很大。对于超过一百万左右的巨大输入，它们可能会更快，但对于小输入，二进制堆可能会明显更快