Course contentsShow
← Computer Science
Lesson 973 of 2,87223. Shortest Path AlgorithmsFree lesson

Dijkstra's with Binary Heap Priority Queue

Optimizing to O((V + E) log V) time complexity using a binary min-heap for the priority queue.

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.