Use two heaps: a max-heap for the smaller half and a min-heap for the larger half.
The max-heap holds all elements less than or equal to the median. The min-heap holds all elements greater than the median.
Keep the heaps balanced: sizes differ by at most 1. If max-heap has more elements, median is its top. If sizes are equal, median is the average of both tops.
When adding a number:
- Add to max-heap first (as a candidate for smaller half).
- Move max-heap's top to min-heap (ensures the largest of the "smaller half" goes to the "larger half" if needed).
- If min-heap becomes larger, move its top back to max-heap.