← Back to the heaps page
Two-Heaps Pattern
A max-heap of the lower half and a min-heap of the upper half, kept balanced — their tops bracket the median at all times.
What to know
- Rebalance whenever sizes differ by more than one.
- Median = a root (odd count) or average of both roots (even count).
- Sliding-window median adds lazy deletion with a hashmap of pending removals.
In the wild: Latency p50 monitoring, real-time analytics, load-balancer median tracking.
Algorithms to reach for
Find median from stream
O(log n)O(log n) insert, O(1) median (LeetCode 295)
Sliding window median
O(n log k)Median of each window with lazy deletes (LeetCode 480)
IPO / scheduling
O(n log n)Alternate two heaps to maximize capital (LeetCode 502)
Practice problems — with full guides
Each problem has its own page: progressive hints, how to approach it, and the full solution.