Find the Running Median (Two-Heap Technique)

Problem: Design a data structure that supports adding numbers from a stream and, at any point, returning the median of all numbers added so far.

Constraints: Numbers arrive one at a time (streaming); you must be able to query the median after each insertion efficiently.

Example: Add 5 -> median = 5 Add 15 -> median = 10 Add 1 -> median = 5 Add 3 -> median = 4

Approach: Maintain two heaps: a max-heap for the lower half of numbers and a min-heap for the upper half, keeping their sizes balanced (differing by at most 1). Insert into the appropriate heap based on comparison with the max-heap's top, then rebalance. The median is either the top of the larger heap (odd count) or the average of both tops (even count). Insertion and median query run in O(log n) and O(1) respectively.