DSA Tracker

Visualize

Find Median from Data Stream

A max-heap for the lower half + a min-heap for the upper half

time O(log n) per addNum, O(1) per findMedianspace O(n)

Split every number seen so far into two halves at the median boundary: the smaller half sits in a max-heap (so its biggest value — the candidate closest to the boundary — is always at the root) and the larger half sits in a min-heap (so its smallest value is at the root). Keeping the two heaps within one element of each other in size means the median is always just the root of the bigger heap, or the average of both roots when they're equal.

Details

Animated on: addNum(1), addNum(2), findMedian() -> 1.5, addNum(3), findMedian() -> 2 — design a structure that supports adding numbers from a stream and finding the running median.

Problem:Find Median from Data StreamHard

A max-heap for the lower half + a min-heap for the upper half

step 1 / 11

1

addNum(1): lower is empty or 1 <= top(lower) — append 1 as a new leaf.

Pseudocode
1FUNCTION addNum(num):
2  IF lower is empty OR num <= TOP(lower): PUSH num TO lower
3  ELSE: PUSH num TO upper
4  IF SIZE(lower) > SIZE(upper) + 1:
5    PUSH POP(lower) TO upper
6  IF SIZE(upper) > SIZE(lower):
7    PUSH POP(upper) TO lower
8FUNCTION findMedian():
9  IF SIZE(lower) = SIZE(upper): RETURN (TOP(lower) + TOP(upper)) / 2
10  RETURN TOP(lower)

← / → step · space play · Home restart

Every step in words

Show all 11 steps
  1. addNum(1): lower is empty or 1 <= top(lower) — append 1 as a new leaf.
  2. addNum(2): compare against lower's top, 1. 2 > 1, so this one routes to upper instead.
  3. 2 pushed to upper as a new leaf.
  4. findMedian(): sizes are equal (1 and 1) — median = (1 + 2) / 2 = 1.5.
  5. addNum(3): compare against lower's top, 1. 3 > 1, so this one routes to upper instead.
  6. 3 pushed to upper as a new leaf.
  7. Upper now has 2 elements to lower's 1 — rebalance: move upper's top over to lower.
  8. Extracted upper's top, 2. Upper is now {3}.
  9. Insert the extracted 2 into lower as a new leaf.
  10. 2 broke max-heap order against its parent — swap up. Lower's new root is 2.
  11. findMedian(): lower has more elements (2 vs 1) — median is simply lower's top, 2.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Find Median from Data Stream in the editorAll Heap problemsBack to roadmap