Median of K Sliding Windows (Extended Practice)

# Python — reusable template
import heapq
from collections import defaultdict

class DualHeap:
    def __init__(self, k):
        self.k = k
        self.lo = []  # max-heap (negate)
        self.hi = []  # min-heap
        self.lo_size = 0
        self.hi_size = 0
        self.trash = defaultdict(int)

    def _prune(self, heap):
        while heap and self.trash[abs(heap[0])] > 0:
            self.trash[abs(heap[0])] -= 1
            heapq.heappop(heap)

    def add(self, num):
        if not self.lo or -self.lo[0] >= num:
            heapq.heappush(self.lo, -num)
            self.lo_size += 1
        else:
            heapq.heappush(self.hi, num)
            self.hi_size += 1
        self._balance()

    def remove(self, num):
        self.trash[num] += 1
        if num <= -self.lo[0]:
            self.lo_size -= 1
        else:
            self.hi_size -= 1
        self._balance()

    def _balance(self):
        while self.lo_size > self.hi_size + 1:
            self._prune(self.lo)
            v = -heapq.heappop(self.lo)
            self.lo_size -= 1
            heapq.heappush(self.hi, v)
            self.hi_size += 1
            self._prune(self.hi)
        while self.hi_size > self.lo_size:
            self._prune(self.hi)
            v = heapq.heappop(self.hi)
            self.hi_size -= 1
            heapq.heappush(self.lo, -v)
            self.lo_size += 1
            self._prune(self.lo)

    def median(self):
        self._prune(self.lo)
        self._prune(self.hi)
        if self.k % 2 == 1:
            return float(-self.lo[0])
        return (-self.lo[0] + self.hi[0]) / 2.0

// C++ template — see sliding window median problem
// Key insight: Track lo_valid_size and hi_valid_size separately from heap sizes

// Java — similar lazy deletion with TreeMap for O(log n) operations:
class Solution {
    TreeMap<Integer, Integer> lo, hi;  // value -> count
    int loSize, hiSize;
    // add/remove manipulate sizes + lazy prune on median access
}

// JavaScript — use SortedList equivalent (binary search insertion)
// Performance: O(k) per operation with array, O(log k) with proper BST