Two Heaps Technique

The idea: maintain two heaps that partition the elements around the median.

$1.$ Max-heap: contains the smaller half of elements. Its root is the largest small element.

$2.$ 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: $O(\log n)$. Space: $O(n)$.