Sliding Window Median: Two Heaps

Concepts: pyTwoHeapMedian, pySlidingWindowMedian, pyLazyDeletion

The two-heap median pattern is the one that gets used as a staff-level filter. If you are interviewing for L5+ data engineer or staff, this problem or a variant of it is likely to appear. The pattern: maintain two heaps — a max-heap for the lower half of seen numbers and a min-heap for the upper half. The median is always derivable from the roots of these two heaps. It is simple in concept and full of edge cases in implementation. Which is exactly why interviewers love it. The Balancing Invariant The invariant that makes everything work: the lower max-heap can have at most one more element than the upper min-heap. Both heaps together contain all seen elements, split at the median. The lower max-heap root is the largest element in the lower half. The upper min-heap root is the smallest elem