Find K nearest Points to Point P in 2-dimensional plane

For just a single query...

Maintain a heap of size k.

For each point, calculate the distance to the point P. Insert that distance into the heap and delete the maximum from the heap if the size of the heap is greater than k.

Running time: O(n log k)

Solution 1 make heap of size K and collect points by minimal distance O(NLogK) complexity.

Solution 2: Take and array of size N and Sort by distance. Should be used QuickSort (Hoare modification). As answer take first K points. This is too NlogN complexity but it is possible optimize to approximate O(N). If skip sorting of unnecessary sub arrays. When you split array by 2 sub arrays you should take only array where Kth index located. complexity will be : N +N/2 +N/4 + ... = O(N).

Solution 3: search Kth element in result array and takes all point lesser then founded. Exists O(N) alghoritm, similar to search of median.

Notes: better use sqr of distance to avoid of sqrt operations, it will be greater faster if point has integer coordinates.

As interview answer better use Solution 2 or 3.