K closest points to the origin

Find the k points closest to the origin by keeping a max-heap of size k, evicting the farthest point whenever the heap grows too large.

The idea

A max-heap of size k keeps the k points with the smallest distances seen so far — not because you want the farthest first, but because the farthest of the kept set is the first one to evict if a closer point turns up. Comparing squared distances avoids an unnecessary square root while keeping the same order.

Code

public static List<(int x, int y)> KClosest(int[] xs, int[] ys, int k) {
    var heap = new PriorityQueue<int, int>(Comparer<int>.Create((p, q) => q - p)); // max-heap by distance
    for (int i = 0; i < xs.Length; i++) {
        int dist = xs[i] * xs[i] + ys[i] * ys[i];
        heap.Enqueue(i, dist);
        if (heap.Count > k) heap.Dequeue();
    }
    var result = new List<(int, int)>();
    while (heap.Count > 0) { int i = heap.Dequeue(); result.Add((xs[i], ys[i])); }
    return result;
}

Tips

• Squared distance preserves ordering and avoids floating-point square roots entirely.
• A max-heap for the smallest k is the mirror image of using a min-heap for the largest k: the eviction target is always the "wrong" extreme of what you are keeping.

In the .NET library

Sorting all n points by distance costs O(n log n); the heap approach costs O(n log k), which wins decisively once k is much smaller than n.