Practical Efficiency of Fibonacci Heaps
Fibonacci Heaps are commonly used in the theoretical analysis of the running time of Dijkstra's algorithm. We take a look at results from two papers that perform experiments on various heap data structures to explore whether Fibonacci heaps are also a good choice in practice.
00:00 Overview of heap data structures
04:14 Lines of code
04:35 Experiment: Dijkstra on US map
06:50 Experiment: Many DecreaseKey
08:01 Conclusions and Sequence Heap