A priority queue removes items by priority rather than by insertion order. The highest-priority or lowest-cost item is processed first.
In Python algorithm practice, a priority queue is usually implemented with heapq.
Core Idea
Each item is stored with a priority. When the algorithm asks for the next item, the priority queue returns the item with the best priority.
This is different from a normal queue, where the oldest item is processed first.
Python Example
import heapq
pq = []
heapq.heappush(pq, (3, "low priority"))
heapq.heappush(pq, (1, "high priority"))
priority, item = heapq.heappop(pq)The popped item is "high priority" because 1 is the smallest priority value.
Common Confusions
In Python, tuples are compared from left to right. (priority, item) works only when ties can be compared safely. If the item values are not comparable, add a counter as a tie-breaker.
A priority queue does not automatically update an existing item’s priority. Many algorithms push a new entry and ignore stale entries when they are popped.
When To Use It
Use a priority queue when the next step should be chosen by cost, distance, urgency, or score. Dijkstra’s algorithm is the standard example.