Sliding window median: how do you maintain median with two heaps as the window slides?

Question presented to candidate: "Given a list nums and a window size k, return the median of every window of k consecutive numbers as the window slides from left to right. Write it in Python, and do better than sorting every window."

What a strong answer should cover:

• Brute force (sort each window, O(n·k log k)) and the sorted-window improvement (O(n·k)).
• Two heaps as in the stream median, plus lazy deletion: a dict of pending removals, live sizes for balancing, and pruning stale tops.
• How to tell which heap the leaving number belongs to (compare with the top of the lower half), and why that is safe with duplicates.
• Honest complexity: O(n log n) time, O(n) worst-case space because stale entries can pile up.
• Python details: heapq is min-only (negate the lower half), collections.defaultdict(int) for counts, bisect for the sorted-window alternative.

Clarifying questions expected:

• For even k, average the two middle values?
• How large are n and k?

Code / implementation expected: Yes — a two-heap class with lazy deletion and a driver that slides the window, in Python 3.