Sliding Window Median

The Idea

A window median wants the two-heap split again — but each slide evicts a value that may be buried anywhere inside a heap, and a heap has no way to reach it.

So do not reach. Record the value as dead in a counter and carry on. Only when a dead value rises to a root does it actually get popped, because the root is the one thing you ever read.

Real-World Example

A hotel's rolling thirty-day rating. A retracted review is struck off the register rather than hunted down in the pile; it only has to be physically pulled when it reaches the top of the stack being read out.

The Code

import heapq

def peek_after_removals(values, removed):
    heap = list(values)
    heapq.heapify(heap)
    dead = {}
    for r in removed:                         # mark, never search
        dead[r] = dead.get(r, 0) + 1
    while heap and dead.get(heap[0], 0):      # clean only at the root
        dead[heap[0]] -= 1
        heapq.heappop(heap)
    return heap[0]

print(peek_after_removals([4, 1, 7, 3], [1]))     # 3
print(peek_after_removals([4, 1, 7, 3], [1, 3]))  # 4

import heapq
heap = [1, 3, 7, 4]      # a valid min-heap
dead = {1: 1}            # 1 has left the window
while heap and dead.get(heap[0], 0):
  dead[heap[0]] -= 1
  ___
print(heap[0])           # should print 3