1Understand
The idea
Split the numbers into a lower half (a max-heap) and an upper half (a min-heap), keeping their sizes equal or off by one. The median is then on top of one or both heaps, available in O(1) at all times, and each insertion costs O(log n) plus a rebalance.
Intuition
Split numbers into a lower half (max-heap) and an upper half (min-heap), keeping sizes equal or off by one. The median is then on top of one or both heaps, O(1) read, and each insertion is O(log n) plus a possible rebalance.
In Python, simulate the max-heap with negated values. The invariant: every element in low ≤ every element in high, and size(low) is size(high) or one larger.
This is the standard "median from data stream" structure.
What you will be able to do
- Maintain size and order invariants
- Read the median from the tops
When to use it
- Median of a data stream
- Balance two halves of the data
2See it
Walkthrough
Median with two heaps
Stream 1, 5, 2, max-heap lows + min-heap highs.
1 / 5
lows stores negatives for max-heap. After 1: lows=[-1], highs=[].
Live template
Complexity: time O(log n) per insert, space O(n)
Each insert O(log n), median O(1), space O(n). Sorting at each step is O(n²) or O(n log n) per query. Two heaps are the intended streaming solution.
Read the walkthrough as text
Running median. Insert 1, then 2, then 3.
- Insert
1into low (max-heap). Median1. - Insert
2: goes to high; rebalance so low has the extra if needed. Heaps: low=[1], high=[2]. Median(1+2)/2. - Insert
3: to high → high=[2,3]; move2to low. low=[2,1], high=[3]. Median2.
Always push to one heap, then peek/compare and rebalance sizes so the invariant holds.
3Recognise it
Kinds of problems (4)
Same pattern, different surfaces. Each row is a problem shape you should recognise, not only the first walkthrough example.
Median of a stream
Example. Median after each number is added.
How. Low half in max-heap (negated), high half in min-heap; rebalance sizes after each insert.
Sliding window median (lazy deletion)
Example. Median of each window of size k.
How. Same two heaps plus delayed deletes in maps; prune stale tops before reading median.
Maximise capital (IPO)
Example. Pick projects with capital and profit constraints.
How. Sort by capital; min-heap affordable by capital; pop max profit from max-heap when affordable.
Split into two balanced halves
Example. Partition so low heap holds lower half and high heap the upper.
How. Stream into low/high with rebalance invariant: low size ≥ high size and low.top ≤ high.top.
Common mistakes
Failure modes the tutor watches for. Open the Common mistake tab in the walkthrough to watch one fail live.
Heaps unbalanced
Why it happens. Medians still “work” if heaps differ by two until you read the wrong top.
How it fails. len(high) exceeds len(low)+1, median read from empty or wrong half.
Fix. After each insert, rebalance so size difference is at most 1 (low has equal or one extra).
Halves out of order
Why it happens. Rebalancing sizes without checking order still yields two piles.
How it fails. max(low)=10, min(high)=8 after moves, halves overlap and median is meaningless.
Fix. If low.top > high.top, move top from one heap to the other, then fix sizes.
Negation forgotten
Why it happens. Negating on push but not on read feels redundant.
How it fails. Median from max-heap stored as -3 instead of 3, off by sign and wrong order.
Fix. Push -x into max-heap; read -heap[0] for the actual largest of the low half.
4Check yourself
Concept check
A short quiz on this lesson before you practise. Optional, and it does not gate coding.
Ready to practise?
Mastery comes from solving. The lesson is optional context.