Stage 1 · Code
Heaps & Priority Queues
Running Median
Two-heap approach for streaming median calculation.
7 min readMastering Data Structures & Algorithms for Software Engineering InterviewsCode
Two Heaps Approach
Maintain max-heap for lower half and min-heap for upper half. Invariant: sizes differ by ≤ 1, all in max-heap ≤ all in min-heap. Median: if equal size, average of tops; else top of larger heap.
Implementation
Gorunning-median-with-two-heaps.go
44 linesLn 1, Col 1Go
Lower = max heap (store negatives). Upper = min heap. Add: push to lower, move max to upper, rebalance sizes. Median from tops. O(log n) add, O(1) median.
Variants
- Sliding window median: Add entering element, remove leaving element (requires heap with delete or lazy deletion).
- Median of two sorted arrays: Binary search partition (O(log min(m,n))).
- Streaming percentile: Multiple heaps or t-digest for approximate percentiles.
- Continuous median: Same two-heap approach, just report median after each add.
Mark this lesson complete to store local progress and unlock a cleaner resume path the next time you visit.