Two Heaps

Sliding Window Median

Like streaming median, but elements also leave the window. Use lazy deletion: mark elements as removed but only actually delete them when they appear at a heap's top. Rebalance after each add/remove.

O(n log n)

O(n)

How It Works

Sliding window median extends the two-heap structure with lazy deletion, because elements now leave the window as well as enter it. Standard binary heaps cannot remove an arbitrary element cheaply, so departures are recorded in a hash map of pending deletions instead. Balance is tracked with logical sizes — counts that exclude pending deletions — and whenever a heap's top matches a pending deletion, it is popped and the map decremented. Since medians are only read from the tops, stale entries buried deeper are harmless.

Each window slide performs one insertion, one logical deletion, and a rebalance, each O(log n) amortized, giving O(n log n) overall for n slides — versus O(n·k) for re-scanning or re-sorting each window. The subtle part is bookkeeping: rebalancing decisions must use logical sizes, not the heaps' physical sizes, or the halves drift out of sync.

Step-by-Step Visualization

Sliding window median, k=3

-1

-3

Window [0..2]

Window[1,3,-1] → sorted [-1,1,3]

Median1

1/3

Code

Java

static double[] medianSlidingWindow(int[] nums, int k) {
  double[] result = new double[nums.length - k + 1];
  // Simplified: sort window each time
  for (int i = 0; i <= nums.length - k; i++) {
    int[] window = Arrays.copyOfRange(nums, i, i + k);
    Arrays.sort(window);
    result[i] = k % 2 != 0 ? window[k/2] : ((double)window[k/2-1] + window[k/2]) / 2;
  }
  return result;
}

Tips & Gotchas

1Like streaming median but elements also leave the window

2Use lazy deletion: mark elements for removal but don't remove immediately

3Rebalance heaps when their tops are invalid

Practice Problems

1Sliding Window Median
2Sliding Window Maximum
3Find Median from Data Stream

About the Two Heaps Pattern

Split a stream of numbers into two halves: a max-heap for the smaller half and a min-heap for the larger half. The median is at the tops of the heaps. Rebalance to keep their sizes within 1 of each other.

Key insight

Need the K largest? Use a min-heap of size K — anything larger than the min gets in. For median, split into two heaps: max-heap for lower half, min-heap for upper half.

Common Heap Interview Problems

Kth Largest Element
Top K Frequent Elements
Find Median from Data Stream
Merge K Sorted Lists
Task Scheduler
K Closest Points to Origin

Frequently Asked Questions

Why not delete elements from the heap immediately?

A binary heap only supports efficient removal at the top; deleting an arbitrary element requires finding it first, which is O(n). Lazy deletion defers the work until the element surfaces at the top, where removal is O(log n), preserving overall efficiency without extra data structures.

Are there simpler alternatives to two heaps with lazy deletion?

An indexed balanced BST or order-statistic multiset (like C++ multiset with an iterator to the middle) gives O(log n) insert, erase, and median access with less bookkeeping. In languages without such containers, a sorted list with binary-search insertion is O(k) per slide but very easy to write — acceptable when k is small.