Why This Matters
Priority queues are the abstraction behind "do the most important thing next." They appear in Dijkstra's algorithm, A* search, event simulation, job schedulers, top-k retrieval, beam search, and retry systems.
The data structure is usually a heap, but the idea is broader: clients care about priority operations, not the storage layout.
Core Idea
A priority queue supports inserting an item with a priority and removing the item with highest or lowest priority.
| Operation | Meaning | Binary heap cost |
|---|---|---|
push(item, priority) | add an item | O(log n) |
peek() | inspect best item | O(1) |
pop() | remove best item | O(log n) |
decreaseKey(item, priority) | improve an existing priority | O(log n) with handles |
Min-priority queues return the smallest priority first. Max-priority queues return the largest priority first.
Non-Example or Failure Mode
Sorting a full list every time you need the next item is not a priority queue. It works on tiny inputs, but repeated sorting often turns a simple scheduler into an avoidable O(n log n) bottleneck.
The other failure mode is updating priorities without handles. In graph algorithms, inserting duplicate entries can be simpler than decrease-key, but then pop must ignore stale entries.
Worked Example
In Dijkstra's algorithm, each queued item is a vertex and its priority is the current best-known distance from the start.
push(start, 0)
while queue is not empty:
vertex, distance = pop_min()
if distance is stale: continue
relax outgoing edges
The queue always exposes the unsettled vertex with smallest tentative distance.
Common Mistakes
| Mistake | Correction |
|---|---|
| Confusing priority queue with queue. | A queue is first-in first-out; a priority queue chooses by priority. |
| Assuming heap array order is sorted. | Only the root is guaranteed best. |
| Ignoring tie-breaking. | Equal priorities can still need stable or deterministic ordering. |
| Updating priorities without a plan. | Use handles, lazy duplicate entries, or an indexed priority queue. |
Diagnostic Questions
| Question type | Question | Answer signal |
|---|---|---|
| Definition | What is the abstraction? | Insert by priority, inspect/remove best priority. |
| Example / non-example | Is a FIFO job queue a priority queue? | No, unless priority is arrival order. |
| Computation | Why is repeated pop from a binary heap logarithmic? | Each removal repairs the heap along height O(log n). |
| Transfer | Why does A* need a priority queue? | It repeatedly expands the frontier state with smallest estimated total cost. |
Exercises
Beginner:
- Decide whether each example needs FIFO, LIFO, or priority behavior: printer jobs, undo stack, shortest-path frontier.
- Give priorities for a retry queue ordered by next retry time.
- Explain the difference between
peekandpop.
Intermediate:
- Implement a min-priority queue using a binary heap.
- Modify top-k selection to use a bounded priority queue.
Challenge:
- Implement lazy duplicate entries for Dijkstra and explain why stale entries must be skipped.
Diagram Recommendation
Type: abstraction-to-implementation diagram.
Caption: "Priority queue operations mapped to a binary heap."
Purpose: Separate the interface clients use from the heap representation underneath.
Next Topics
References
- Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms (4th ed., 2022). Ch. 6.
- MIT OpenCourseWare. 6.006 Introduction to Algorithms, Spring 2020.
- Sedgewick and Wayne. Algorithms (4th ed., 2011). Priority queues.