Kth largest in an array, without sorting

Scan the array once and keep only the k largest values seen so far in a min-heap. The root is the smallest of those k, which is the kth largest. Whenever the heap grows to k+1, pop the root: it has k bigger values above it, so it can never be the answer.

Try:
CALL
1 / 1

Code

The highlighted line runs next. Sift-up and sift-down steps happen inside the library's push and pop, so they stay on the push and pop lines.

Min-heap (heap)

tree view every parent ≤ its children, so the smallest kept value is on top

array view children of index i are 2i+1 and 2i+2

Array scan

nums orange = current · blue = kept in heap · struck = dropped · dashed = not reached

values seen so far, largest first (for checking only; the algorithm never sorts)

Cost: each of the n values does one push and maybe one pop on a heap of at most k+1 items, so O(n log k) time and O(k) memory. Sorting would be O(n log n).

Dry-run trace

Every step as a row. Click a row to jump there.

#ActioninumDetailheap (array)size

Keyboard: ← → step, Space play or pause. Up to 14 numbers, k ≤ 8. Real libraries may order the heap array slightly differently, but the root is always the same.