The idea: maintain two heaps that partition the elements around the median. Max-heap: contains the smaller half of elements. Its root is the largest small element.
Min-heap: contains the larger half of elements. Its root is the smallest large element. The median is: - The root of the larger heap (if sizes differ) - Average of both roots (if sizes are equal) Insertion goes into one heap, then you rebalance to keep sizes equal (or differ by 1). Time: . Space: .