DSA TrainerFoundations · Unit 11
Heaps and Priority Queues
Some problems keep asking the same question as the data changes: what is the smallest value right now? Or the largest, or the highest-priority? A hospital takes the most urgent patient next, not the one who arrived first. A task runner grabs the highest-priority job, even as new jobs keep arriving.
You could re-sort the whole collection every time something changes, but that is O(n log n) per change, wildly wasteful when you only ever need the one item at the extreme. A heap is the structure built for exactly this: it keeps the minimum (or maximum) instantly available while still letting you add and remove items quickly.
A heap is also how a priority queue is built, the "serve the most important first" cousin of the plain queue from earlier. This unit covers what a heap guarantees, what it costs, the one thing people wrongly assume about it, and how to spot a problem that wants one.
You’re not signed in. Your progress here won’t be saved.
The problem: always needing the extreme
Picture a stream of tasks, each with a priority, arriving and being handled over time. At every moment you need to pull the highest-priority task, but new tasks keep showing up and changing what "highest" is.
One option is to keep the list sorted, but re-sorting after every insertion is O(n log n) each time. Another is to scan the whole list for the max on every pull, which is O(n) per pull. Both repeat a lot of work just to find one item. There should be a structure that keeps the extreme cheaply available as things change, and there is.
You repeatedly need the largest value from a collection while new values keep getting added. Why is re-sorting the whole collection after each addition a poor approach?
The drills and graded test are premium
The lessons above are free. The interactive practice that turns recognizing the pattern into recalling it on a blank page unlocks with premium:
- ✓2 applied drills: train spotting when the concept applies
- ✓A 5-question graded test to clear the unit
- ✓The full guided problem ladder with faded hints, plus the cold-read capstone
From $6/month. Cancel anytime.