Why This Matters
The heap invariant has a direction. Choose the wrong direction and your top-k, scheduler, median tracker, or graph frontier becomes awkward or inefficient.
Min-heaps are natural for smallest-distance, earliest-deadline, and soonest-event problems. Max-heaps are natural for largest-score, highest-priority, and maximum-value problems.
Core Idea
| Heap type | Root stores | Common use |
|---|---|---|
| Min-heap | smallest key | Dijkstra, event times, k largest with bounded heap |
| Max-heap | largest key | priority scheduling, k smallest with bounded heap |
| Double-ended priority queue | min and max | range tracking, online medians, bidirectional extremes |
A min-heap invariant says every parent key is <= its children. A max-heap invariant reverses it.
Non-Example or Failure Mode
A max-heap is not the right direct tool for Dijkstra's algorithm, because Dijkstra repeatedly needs the smallest tentative distance. You can invert priorities, but the conceptual queue is still min-priority.
Worked Example
To keep the 5 largest values in a stream, use a min-heap of size 5.
if heap has fewer than 5 items: push(x)
else if x > heap.min:
pop_min()
push(x)
The smallest value in the heap is the cutoff. Anything smaller cannot enter the current top 5.
Common Mistakes
| Mistake | Correction |
|---|---|
| Using max-heap for k largest stream values. | A bounded min-heap makes replacement cheap. |
| Expecting min and max from one binary heap. | A normal binary heap exposes only one extreme efficiently. |
| Thinking heap direction changes complexity. | Min and max heaps have the same asymptotic costs. |
Diagnostic Questions
| Question type | Question | Answer signal |
|---|---|---|
| Definition | What changes between min-heap and max-heap? | The parent-child comparison direction. |
| Example / non-example | Which heap tracks earliest events? | Min-heap by timestamp. |
| Computation | What is the root of max-heap [10, 7, 9, 2]? | 10. |
| Transfer | Why use a min-heap to keep largest k items? | The root is the current cutoff and can be replaced. |
Exercises
Beginner:
- Convert the min-heap invariant into the max-heap invariant.
- Choose min-heap or max-heap for earliest task deadline.
- Choose min-heap or max-heap for highest bid.
Intermediate:
- Track the 3 smallest stream values with a bounded heap.
- Explain why one ordinary heap cannot return both min and max in
O(log n).
Challenge:
- Design a median tracker using one max-heap for the lower half and one min-heap for the upper half.
Diagram Recommendation
Type: side-by-side heap trees.
Caption: "The same keys arranged as a min-heap and a max-heap."
Purpose: Show that direction, not shape, is the distinction.
Next Topics
References
- Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms (4th ed., 2022). Ch. 6.
- MIT OpenCourseWare. 6.006 Introduction to Algorithms, Spring 2020.