Algorithms and Data Structures · Senior · Question 56 of 75
How do you maintain the running median of a stream efficiently?
- 1Insert into a sorted array and read the middle
- 2Keep the running average, which equals the median
- ✓Correct answer: A max-heap for the lower half, a min-heap for the upper
Explanation
Keep the heaps balanced in size; the median is one of the roots or their average. Each insert is O(log n). A sorted array needs O(n) shifting per insert, and the average is not the median.