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.)
- Input: list of points.
- Initialize a priority queue $Q$, where priority is measured according to the distance from origin (larger distance is higher priority).
- For each point $p$:
- Add $p$ to $Q$.
- If $Q$ contains $n+1$ points, remove the point with highest priority.
- 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.