Where it runs
1. The problem
In the previous lessons one heap handed you the smallest value. Here there are two heaps, and the question is different: which value is in the middle of all the data so far? The answer has to be updated after every new number.
Numbers arrive in a stream, for example latency samples. After each number you need the current median. The median is the value in the middle when everything so far is sorted. It shows the typical value well: one huge spike moves the mean (the ordinary average) a lot and barely moves the median. For the samples 10, 11, 12 and 1000, the mean is above 250, while the median is 11.5.
You could keep a sorted array and read its middle. Reading is easy, but every new number has to be inserted in its place by shifting elements. One insert costs O(n), and on a long stream that is too slow. You need the middle without keeping everything in order.
This step is part of the paid track
The first 33 steps are open to everyone: lesson, exercise and tests. This one opens with full access. Start with a free account and the free steps.
Create a free accountSee what is includedRecognise it
Say these words and it is this pattern
- always need the current smallest/largest
- top k elements
- merge k sorted lists
- running median while items keep arriving
- priority queue / most urgent next
Looks similar, isn't
- Fast sort (merge / quick)
Sorting gives a full order once. A heap gives the front repeatedly, while data still arrives.
- Binary search tree
A search tree orders every pair of nodes. A heap only promises the root.
- Monotonic deque (sliding window max/min)
A deque can drop the element that just expired. A heap has no cheap way to do that.
- Dijkstra's algorithm
Dijkstra is the best-known user of a heap. This page is about the container itself.
n up to 1e6 gives O(log n) per push or pop. Reading the top alone is O(1).
On LeetCode
Problems that ask for the median or another middle value while numbers keep arriving. A max-heap holds the lower half and a min-heap the upper half, and their roots give the middle.
The lesson's runningMedian as a class with addNum and findMedian.
The same two heaps, plus lazy deletion, so a value leaving the window is marked in a map and dropped once it reaches a root.
Two heaps split at the ith best location, and each get moves that split one place further.