Practice: The Three Campsites Closest to the Trailhead

Campsites lie at kilometre marks along a trail: find the three nearest the trailhead's mark, then choose a method for a feed of a million sites.

A question about the k closest items is a k smallest question in disguise, and choosing how to answer it depends on how the items arrive. A trail's trailhead sits at kilometre 12, and campsites lie at kilometres 3, 9, 14, 20, 11, 25 and 13. Find the three campsites nearest the trailhead with a heap, and say which heap and of what size. Then choose a method for each of three situations: these seven sites, asked once; a feed of a million sites that keeps arriving; and only the single fiftieth-nearest site of a list already in memory.

Show the answer and a solution

11 and 13, each 1 km away, and 14, 2 km away. The distances are 9, 3, 2, 8, 1, 13 and 1, and the three nearest are the three smallest distances, so the heap throws away the largest distance: a max-heap of size 3, keyed by distance. Python's heapq becomes one by pushing the distance negated. The trace lists the heap farthest first, so the first cell is the site the next closer one replaces.

A max-heap of three distances from kilometre 12

Inputsites 3 9 14 20 11 25 13, trailhead at 12; cells listed farthest first

Site 3, 9 km
1. 3
Site 3 goes in, 9 km away
Site 9, 3 km
1. 3
2. 9
Site 9 goes in, 3 km away
Site 14, 2 km
1. 3
2. 9
3. 14
Site 14 goes in; the heap is full, with site 3 the farthest
Site 20, 8 km, dropped 3
1. 20
2. 9
3. 14
Site 20 at 8 km goes in, and site 3 at 9 km, the farthest, is dropped
Site 11, 1 km, dropped 20
1. 9
2. 14
3. 11
Site 11 at 1 km goes in, and site 20 is dropped
Site 25, 13 km, dropped 25
1. 9
2. 14
3. 11
Site 25 at 13 km is the farthest of the four, so it is dropped at once
Site 13, 1 km, dropped 9
1. 14
2. 11
3. 13
Site 13 at 1 km goes in, and site 9 at 3 km is dropped

ResultThe three nearest campsites are 11, 13 and 14.

The listing breaks the tie between sites 11 and 13 by the site's number, since both are 1 km away.

campsites.pypy

import heapq

trailhead = 12
sites = [3, 9, 14, 20, 11, 25, 13]
heap: list[tuple[int, int]] = []
for site in sites:
    heapq.heappush(heap, (-abs(site - trailhead), site))
    if len(heap) > 3:
        heapq.heappop(heap)
nearest = sorted((-negated, site) for negated, site in heap)
print("three nearest:", [site for _, site in nearest])
print("distances:", [distance for distance, _ in nearest])

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

three nearest: [11, 13, 14]
distances: [1, 1, 2]

The three situations each want a different method. Quickselect is the partition step of quicksort repeated on one side only, as the Quicksort topic in Algorithms shows.

Choosing a method for a k closest question
Situation	Method	Why	Cost
Seven sites, asked once	Sort by distance	Simplest, and n is tiny	O(n log n)
A feed of a million sites	Max-heap of size k	Never holds more than k, works as sites arrive	O(n log k) time, O(k) space
Only the 50th-nearest, list in memory	Quickselect	Finds one rank without ordering the rest	O(n) on average, O(n²) worst

Heaps

← → move through sections and cards