Your two-heap machine handles a stream beautifully. Numbers arrive, you route them to the correct heap, you rebalance, and the median is always one O(1) read away. The stream can be infinite — a million numbers, a billion — and the structure never breaks a sweat.

But what if the question changes? Instead of "what is the median of everything so far,“ someone asks: ”what is the median of the last k numbers?"

This is the sliding window median. A window of fixed size k moves across the data. When a new number enters from the right, the oldest number departs from the left. The window always contains exactly k elements, and you need the median of just those k — not the entire history. This is how real monitoring systems work: you care about the last five minutes of server response times, not the last five years. You care about the recent trend, not the ancient past.

Arrivals are easy. You already know how to insert into the correct heap and rebalance. You have practiced it. The routing rule is clean, the balance invariant is enforced, and the whole process costs O(log n). Nothing about arrivals changes in the windowed setting.

The new constraint is departures — and departures are where heaps fight back.

A heap is optimized for one thing: accessing the extreme element. A max-heap gives you the largest value in O(1) and removes it in O(log n) via extractMax. A min-heap does the same for the smallest. These operations are fast because they always work with the root — the element at position zero, the one the entire tree is organized around.

But what about removing an element from the middle of the heap? An element that is neither the root nor a leaf, but buried somewhere in the interior? There is no removeByValue in a heap's API. A heap is indexed by position (parent at i, children at 2i+1 and 2i+2), not by value. To find an arbitrary element, you must scan the entire backing array — O(n) — and then sift to restore the heap property. The very data structure that makes insertion fast makes arbitrary removal slow.

Here is the concrete nightmare. Your window is [1, 3, 5, 7] and the window is about to slide right. Watch what happens to the element that departs — and notice where it gets stuck.

The departed element is stuck inside the heap. We cannot efficiently remove it from the middle. So instead of fighting the data structure, we will work with it.

First, predict what happens if we try to remove from the interior. Then find the stuck node and mark it.

The instinct is to solve the removal problem directly — find the element, extract it, repair the heap. Engineers want to fix things. But what if the right move is not to fix the removal, but to surrender the need for it entirely?

Instead of physically extracting the departed element, you mark it. Keep a record — “this value has left the window.” The element stays in the heap. You know it is there. You know it does not belong. But you leave it alone. It is a ghost: present in the data structure, absent from the logical window.

This sounds dangerous. A heap full of ghost elements that do not belong — how can that possibly produce correct answers? The insight is that position matters. A ghost buried in the interior of the heap is harmless. It cannot affect the root. It cannot be read as part of the median. It just sits there, occupying a spot, participating in the heap property, minding its own business, and never being seen by anyone who matters.

The only dangerous ghost is one that reaches the top. If a departed value sits at the root of either heap, it will be returned as part of the median — and that answer will be wrong. So the rule is simple: before reading the median, check if the root is a ghost. If it is, extract it. Check again. Keep pruning ghosted roots until the top of each heap is a living, window-resident element.

You marked a ghost in the interior. It was harmless there. But what happens when a ghost reaches the top of a heap — the position that feeds directly into the median?

Predict the corruption, feel the glitch, and then destroy the ghost.

Time to experience the full lifecycle. Below are two heaps with 10 nodes total. Some of these nodes are ghosts — elements that departed the window but remain stuck in the heap.

Cross-reference each heap node with the current window. If a node's value is not in the window, it is a ghost. Find all three.

All three ghosts are marked. But not all ghosts are equally dangerous. Interior ghosts sit harmlessly inside the heap — they can never be read as the median. Only a ghost at the top corrupts the answer.

Tap the dangerous ghost to destroy it. Tap an interior ghost and you will see why it is harmless.

One last subtlety. What happens when the window contains duplicate values and one copy departs?

You have hunted ghosts, triaged them, and discovered the duplicate trap. Now connect everything to the pruneTop() function that makes it all work.

The strategy you just practiced has a name: lazy deletion. Instead of paying the cost of removal immediately when an element departs, you defer it. You record the departure in a ghost map and only pay the actual heap-removal cost when (and if) the ghost reaches the root and threatens the answer.

The amortized analysis is clean. Every element enters a heap exactly once — O(log n). Every element is eventually extracted from a heap exactly once — O(log n), whether that extraction happens immediately or lazily. The ghost map operations — incrementing a count on departure, decrementing on extraction, checking ghostMap.has(root) before reading — are all O(1) hash-map operations. The total work per window slide is O(log n) amortized, no worse than a single insertion.

There is one subtlety that catches people: duplicate values. If the window contains two copies of 7 and one departs, you need to know that one 7 is a ghost and one is alive. A Set cannot express this — it only knows "is 7 ghosted or not." You need a Map<number, number> that tracks ghost counts. When a value departs, increment its count. When you prune a ghost from the root, decrement. When the count reaches zero, delete the key. This is the difference between "value 7 has departed“ and ”one instance of value 7 has departed" — and with duplicate-heavy data, the distinction is the difference between a correct answer and a subtle, intermittent bug.

Lazy deletion is not a trick unique to two-heap sliding windows. It is a general systems principle that appears everywhere performance-sensitive code meets expensive removal.

Dijkstra's algorithm often uses a “lazy” priority queue: instead of decreasing the key of an existing entry (which requires finding it), you simply insert a new entry with the updated priority. Stale entries are ignored when popped by checking if the node has already been finalized. Same principle — mark instead of remove, prune on access.

LRU caches mark entries as stale during invalidation rather than scanning the eviction list. Database engines use tombstone markers to defer physical row deletion until a compaction pass. Even garbage collectors embody the idea: objects die when their last reference disappears, but memory is not reclaimed until the collector runs.

The common thread is always the same: when the cost of immediate removal is higher than the cost of tolerating stale data, you defer. You pay a small bookkeeping cost (the ghost map, the tombstone, the version counter) to avoid a large structural cost (scanning, sifting, compacting), and you reclaim the real cost later — amortized across many operations, paid only when the stale data actually threatens correctness.

You now have the complete sliding window median: two heaps with a balance invariant, a routing rule, and lazy deletion with pruneTop. The machinery is solid. The next screen steps back from how and asks the harder question: when should you reach for this pattern?