Pattern 3: Two heaps (median of a stream)
Finding the median seems to require the data sorted. But what if it arrives one at a time, in an endless stream, and you need the median after every insertion? Sorting everything every time would be very expensive. The elegant solution: two heaps.
Try it first: Find Median from Data Stream
Before reading the theory, try to solve it. You can start with brute force, you can fail — the point is to feel the problem. The theory comes right below.
The numbers arrive one at a time (a stream). Return the list of medians after each number inserted. (The median of an even number of elements is the average of the two central ones.)
Example: [1, 2, 3] → [1, 1.5, 2]. [5, 15, 1, 3] → [5, 10.0, 5, 4.0].
Tried it? Re-sorting the list at every number is O(n log n) per insertion. The theory below keeps the median accessible in O(1), with O(log n) insertions.
The theory: split into two balanced halves
The median is the "middle" of the sorted data. The clever idea: you do not need everything sorted — you only need to know where the middle splits. So keep the numbers in two halves:
baixo: the smaller half, in a max-heap (its largest at the top — the largest of the small ones).alto: the larger half, in a min-heap (its smallest at the top — the smallest of the large ones).
If the two halves are balanced in size, the median sits right on the border between them — at the tops of the two heaps:
... 1 3 5 | 8 9 12 ...
(max-heap baixo) (min-heap alto)
top=5 top=8
median = top of baixo (if baixo has 1 more → odd)
= (top baixo + top alto)/2 (if equal sizes → even)
For each new number, you insert it and rebalance the sizes (moving the top of one heap to the other if needed), keeping the size difference at most 1. The tops always give the median.
on inserting x:
push x onto `baixo` (max-heap)
move the top of `baixo` to `alto` (ensures baixo <= alto)
if `alto` became larger than `baixo`:
move the top of `alto` back (rebalances the sizes)
median: top of baixo (odd) or the average of the two tops (even)
Why is it O(log n) per insertion and O(1) on query?
Each insertion does a few push/pop on the heaps — O(log n) each. The median is just looking at the tops — O(1). Compared to "sorting every time" (O(n log n) per insertion) or maintaining a sorted list with insertion (O(n)), two heaps are unbeatable for a stream.
| Approach | Insert | Query the median |
|---|---|---|
| Re-sort everything | O(n log n) | O(1) |
| Sorted list (insert in place) | O(n) | O(1) |
| Two heaps | O(log n) | O(1) |
The lesson: balance between two structures
The "two heaps" pattern is a case of a more general idea: keeping two extremes balanced so that the information you want (here, the median) is always accessible at the border. The max-heap holds the top of the lower half; the min-heap, the bottom of the upper half. Balancing the sizes keeps the median "trapped" between the two tops.
In Python, there is no max-heap: the trick is to store the negated values in
heapq(so the smallest negated is the largest real one). In JS, just invert the comparator ((a, b) => b - a).
🧠 Review quiz
0/41. Why do two heaps allow finding the median without sorting everything?
2. Which heap holds the SMALLER half of the numbers, and what sits at its top?
3. Why is it necessary to rebalance the sizes of the two heaps on each insertion?
4. What are the complexities of inserting and of querying the median with two heaps?
Summary
- Two heaps: max-heap of the smaller half + min-heap of the larger half, balanced in size.
- The median sits at the tops: top of the max-heap (odd) or the average of the two tops (even).
- Insert O(log n), query O(1) — ideal for streams.
- In Python, simulate a max-heap with negated values; in JS, invert the comparator.
Last stop: the synthesis of the Heap section and the quiz before the exam.