0
Challenge · 60Heaps & Top-K

Two heaps and the running median

Heapsused in ~55% of apps

The median is the value in the middle, which sounds like it needs everything sorted. It does not. Split the values into a smaller half and a larger half, keep the two halves the same size, and the answer is always sitting on the two inside edges.

Core idea. Hold the smaller half in a max heap and the larger half in a min heap, so the two values nearest the middle are both on top. Keep the sizes within one of each other. The median is then read from one or two slots, with nothing sorted and nothing scanned.
Playground, this isn't a screenshot
two heaps, and the median between them
smaller half, biggest on top
empty
larger half, smallest on top
empty
median...
two heaps back to back. The left holds the smaller half with its LARGEST on top, the right holds the larger half with its SMALLEST on top
step 1 of 13

Neither heap is sorted. Only the two tops are ever read, which is exactly the information a median needs.

↑ play a little first, then dig in