Algorithms and Data Structures · Senior · Question 66 of 75
What is the main advantage of Dijkstra with a Fibonacci heap over a binary heap?
- ✓Correct answer: Amortized O(1) decrease-key: O(E + V log V)
- 2It needs no priority queue at all to run
- 3It also works correctly with negative weights
Explanation
On dense graphs this beats O((V + E) log V). In practice binary heaps (often with lazy deletion instead of decrease-key) are usually faster because Fibonacci heaps have large constants.