Complexity of closest set of points in plane problem

Question

Given a set of points on a plane find the set of $n$ points that are closest to the origin. (Points are pairs of integers.)

1. Input: list of points.
2. Initialize a priority queue $Q$, where priority is measured according to the distance from origin (larger distance is higher priority).
3. For each point $p$:
   • Add $p$ to $Q$.
   • If $Q$ contains $n+1$ points, remove the point with highest priority.
4. Return $Q$.

The priority queue is implemented using a heap.

I'm thinking the runtime is $O(n + k \log n)$, and space is $O(n + m)$. Where $n$ is the number of points examined, $m$ is the number of points being returned and $k$ is $\max(0, n - m)$. Space is both the priority queue and the output.

My understanding is that a heap can be constructed in $O(n)$ hence the $O(n)$ in the runtime complexity. I find it hard to reason why heap construction, which has an upper bound $O(n \log n)$ can be reduced to $O(n)$, but $k$ deletions should be $O(k \log n)$.

I might be overthinking this, but thought I would ask.

Answer 1

There seems to be some confusion regarding parameters. There is $n$, which is the number of points we wish to return; and there is another parameter, let's say $N$, which is the number of points in the input. Assuming that $N \geq n$, the output would consist of $n$ points, so we can dispense with your $k$.

Since the heap contains at most $n$ points, all operations take $O(\log n)$ time. Therefore the running time can be upper-bounded by $O(N\log n)$. It should be easy to construct matching hard instances which show that the worst-case time complexity is indeed $\Theta(N\log n)$.

Regarding space consumption, the usual convention is to measure only the "work tape", that is, only the auxiliary space taken by the procedure, without the input and output. In this case, this is only the heap, which uses up $\Theta(n)$ space.