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