Pattern visualizer

Find Median from Data Stream

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. 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..

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)step 1 / 11

line 2

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

Where to practice Heap

Practice Heap problems All Heap problems Back to roadmap