Dijkstra's with Binary Heap Priority Queue
What you'll learn: How using a binary min-heap as Dijkstra's priority queue dramatically improves performance to O((V + E) log V) time complexity.
The Performance Bottleneck
In the previous lesson, you saw Dijkstra's with an array-based priority queue, which requires O(V) time to extract the minimum distance node each iteration. Across all V iterations, this alone costs O(V²) time—slow for large graphs.
Binary Heap to the Rescue
A binary min-heap is a tree-based data structure that maintains the smallest element at its root and supports two key operations efficiently:
- Extract-min: Remove and return the smallest element in O(log V) time
- Decrease-key: Update a node's priority when we relax an edge in O(log V) time
The Improved Complexity
With a binary heap priority queue:
- Initialization: O(V) to add all vertices to the heap
- Extract-min: Called V times, each O(log V) → O(V log V) total
- Decrease-key (relaxation): Called up to E times (once per edge), each O(log V) → O(E log V) total
Total time complexity: O((V + E) log V)
For sparse graphs where E ≈ V, this is essentially O(V log V)—a massive improvement over O(V²) for dense graphs!
The Trade-off
You gain speed but need slightly more complex heap operations. The heap maintains vertices ordered by their current tentative distances, automatically bubbling the nearest unvisited vertex to the top for extraction.
Key Takeaway: Using a binary min-heap as the priority queue reduces Dijkstra's time complexity from O(V²) to O((V + E) log V), making it practical for large, sparse graphs by efficiently finding the next closest vertex.