Algorithms / Priority Queue Patterns
Least You Need to Know: Priority Queues, Scheduling, and Lazy Updates
A priority queue turns a heap into an algorithmic tool: keep many candidates, then repeatedly extract the currently best one. This pattern appears in scheduling, event simulation, shortest-path style relaxations, and systems that reinsert improved priorities over time.
Least you need to know
- A priority queue stores candidates ordered by priority, not by arrival time.
- Extract-min or extract-max returns the current best candidate under the chosen rule.
- Some algorithms allow stale heap entries and discard them when popped if a fresher record already exists.
- The key question is what priority key makes the next extraction meaningful.
- Priority queues support dynamic frontiers better than repeated rescans.
Key notation
- extract-min — remove candidate with smallest key
- stale entry — heap record no longer matches newest best-known value
- priority key — numeric value used to order the queue
Worked example
- Suppose servers receive jobs with different deadlines or costs.
- Push each job into a priority queue keyed by the rule the algorithm cares about.
- Pop the best candidate, process it, and possibly push updated follow-up work.
- If an old record remains in the heap after an update, discard it when popped instead of trying to edit the heap in place.
Common mistakes
- Students often assume a priority queue returns items in insertion order when priorities tie or change.
- Students often forget to define what the priority key should be.
- Students often try to eagerly delete every stale record instead of filtering on pop.
How to recognize it
- There is a changing frontier of candidates and you repeatedly choose the best one now.
- The next step depends on a numeric priority rather than simple queue order.
- Candidates may be inserted again with improved or updated keys.
Next recommended lesson
Continue through this topic with Least You Need to Know: Queues, FIFO Order, and Level-by-Level Simulation.
Least You Need to Know: Queues, FIFO Order, and Level-by-Level SimulationRelated lessons
Keep going with nearby lessons in the same topic.