Find Median from Data Stream

Maintain two partitions rather than sorting the entire stream after each insertion. The lower half lives in a max-heap and the upper half in a min-heap. Preserve two invariants: every lower value is at most every upper value, and heap sizes differ by at most one. Insert a new number into the lower heap if it is no greater than its top, otherwise into the upper heap; then move one top value across if a heap is too large. For an odd total, the median is the top of the larger heap. For an even total, average both tops using a wide numeric type to avoid overflow before division. Test values arriving sorted, reverse sorted, duplicates, negatives, and one item. Insert is O(log n), querying the median is O(1), and storage is O(n). Mention that deletion or sliding-window medians need lazy deletion or indexed structures, not this simple version alone.