Implement the heaps such that the max-heap stores the lower half and the min-heap stores the upper half, ensuring the max-heap's top is always ≤ the min-heap's top.

After each insertion, rebalance the heaps if their sizes differ by more than 1 by moving elements between them.

For odd total elements, the median is the top of the larger heap; for even, it's the average of both heaps' tops. Optimize rebalancing to run in O(log n) time per operation.