Heaps & Priority Queues
The problem
Some problems don't need a fully sorted collection — just fast, repeated access to the current smallest or largest item as the collection keeps changing (the next task to run, the cheapest unvisited node) — sorting the whole thing on every change is wasteful when only the extreme value is ever needed.
Why now
Trees already gave a structure with fast, ordered access, but a balanced search tree keeps everything ordered, which is more guarantee than 'always know the minimum' actually requires. A heap is a deliberately weaker, cheaper tree structure — only the root is guaranteed to be the minimum (or maximum) — trading full ordering for a faster insert.
Mental model
A heap is a tree that only enforces one rule: every parent is smaller (or larger) than its children — nothing is said about how siblings compare, which is exactly the slack that makes insert and remove-min cheaper than a fully sorted structure. A priority queue is the abstract interface (insert, get-min); a heap is simply the concrete, efficient way most languages implement it.
Requires
- TreesComputer Science Fundamentals
A heap is a specialized, weakly-ordered tree — every heap operation (sift-up, sift-down) is a restricted tree operation exploiting the one parent-child ordering rule, so you need the general tree structure and traversal already understood.
- Arrays & ListsProgramming Fundamentals
A heap is almost universally implemented as an array with implicit parent/child index math (2i+1, 2i+2), not as a pointer-based tree; you need array indexing fluency for that representation to make sense.
Unlocks
Used in
- Priority queues in task schedulers and event simulations
- Dijkstra's shortest-path algorithm, which repeatedly needs the cheapest unvisited node
- Heap sort, and the classic 'find the k largest/smallest elements' family of problems
- Median-maintenance problems using two heaps (a max-heap and a min-heap) in tandem
Projects
- Implement a min-heap from scratch using an array, with insert and extract-min operations maintaining the heap property
- Solve the 'k largest elements in a stream' problem using a heap and explain why it beats sorting the whole stream repeatedly
Examples
- extract-min on a heap of n elements is O(log n) — sift the new root down to restore the heap property, the same halving-depth idea as any balanced tree
- A task scheduler using a min-heap keyed by deadline always knows the most urgent task in O(1), and can insert a new task in O(log n)
Resources
- Heaps — MIT 6.006course
Mastery checklist
- I can implement a min-heap or max-heap from scratch using an array
- I can explain why extract-min is O(log n) and peek-min is O(1)
- I can solve a 'top k elements' problem using a heap
- I can explain why a heap is a weaker guarantee than a fully sorted structure, and why that's the point