K closest points, with a size-k max-heap

Walk through the points once and keep the k closest seen so far in a max-heap ordered by distance. The root is the farthest of those k. When a (k+1)th point arrives, pop the root: it is the one point that can't be in 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.

X-Y plane

not checked yet current point kept in heap heap root (farthest kept) dropped answer

Max-heap (by dist²)

tree view big number = dist², small = the point

array view

Why squared distance? √ only changes the size, not the order: if a² < b² then a < b. Skipping it keeps the math in whole numbers. Why a max-heap? We need quick access to the worst of the k we're keeping. Cost: O(n log k) time, O(k) memory.

Dry-run trace

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

#Actionpointdist²Detailheap (dist²)size

Keyboard: ← → step, Space play or pause. Up to 12 points with coordinates from -20 to 20. The answer may be returned in any order.