K Closest Points

The Idea

You want the k nearest points out of n, and n may be huge. Hold exactly k candidates in a heap ordered so the farthest one sits at the root.

Every new point pushes in; if the heap now holds k+1, evict the root. Squared distance is enough — the square root would not change any comparison.

Real-World Example

A lifeboat crew keeping a board of the five nearest distress calls. A new call goes up and the most distant one comes down; the board is never longer than five, however busy the night.

The Code

import heapq

def k_closest(points, k):
    heap = []                                  # a max-heap, faked by negating
    for x, y in points:
        d = x * x + y * y                      # squared distance orders the same way
        heapq.heappush(heap, (-d, x, y))
        if len(heap) > k: heapq.heappop(heap)  # evict the farthest one held
    return sorted((x, y) for _, x, y in heap)

print(k_closest([(1, 3), (-2, 2), (5, 8), (0, 1)], 2))   # [(-2, 2), (0, 1)]

import heapq

heap = []
for x, y in [(1, 3), (-2, 2), (5, 8), (0, 1)]:
  heapq.heappush(heap, (___, x, y))
  if len(heap) > 2: heapq.heappop(heap)
print(sorted((x, y) for _, x, y in heap))   # should print [(-2, 2), (0, 1)]