Learn
Practice
Newsletter
Resources
Mobile
New
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Find Median from Data Stream
Bookmark
Input
Example 1
Example 2
Example 3
Custom
numbers
=
[1, 2, 3]
stream:
1
2
3
keep two balanced halves, the median sits at the boundary
stream:
1
2
3
keep two balanced halves, the median sits at the boundary
stream:
max-heap
· lower half
min-heap
· upper half
size =
0
size =
0
medians:
1
2
3
max-heap
keeps the lower half,
min-heap
the upper half
stream:
max-heap
· lower half
min-heap
· upper half
size =
1
size =
0
medians:
1
2
3
lower half empty →
1
starts the max-heap
stream:
max-heap
· lower half
min-heap
· upper half
size =
1
size =
0
medians:
1
2
3
1
odd count → median = top of lower half =
1
stream:
max-heap
· lower half
min-heap
· upper half
size =
1
size =
0
medians:
1
2
3
1
read num =
2
stream:
max-heap
· lower half
min-heap
· upper half
size =
1
size =
1
medians:
1
2
3
1
1.5
median = (
1
+
2
) / 2 =
1.5
stream:
max-heap
· lower half
min-heap
· upper half
size =
1
size =
1
medians:
1
2
3
1
1.5
read num =
3
stream:
max-heap
· lower half
min-heap
· upper half
size =
1
size =
2
medians:
1
2
3
1
1.5
3
> top 1 → upper half
stream:
max-heap
· lower half
min-heap
· upper half
size =
2
size =
1
medians:
1
2
3
1
1.5
2
odd count → median = top of lower half =
2
stream:
max-heap
· lower half
min-heap
· upper half
size =
2
size =
1
medians:
1
2
3
1
1.5
2
final median = 2 after 3 numbers
algo
master
.
io
Step:
Start: stream = [1, 2, 3], track the median after every number
0 / 12
Input
Example 1
Example 2
Example 3
Custom
numbers
=
[1, 2, 3]
0 / 12
algo
master
.
io
Step:
Start: stream = [1, 2, 3], track the median after every number
