Find k closest stars in 3D space.

You have a huge set of stars as three dimensional coordinates. How would you find the k closest stars?


Approach:
S1 = {x1,y1,z1};
S2 = {x2,y2,z2};
S3 = {x3,y3,z3}; and so on..


1. First sort S[1..n] according to x coordinate. Then for every S[i] find the distance from k points in the front and then k points in the back by maintaing a max-heap of size k.
2. Secondly sort S[1..n] according to y coordinate. Then for every S[i] find the distance from k points in the front and k points in tha back and updating the k-size max-heap defined above if required.
3. Now sort S[1..n] according to z coordinate. And for every S[i] find the distance from k points in the front and k points in tha back and update the k-size max-heap if required.
4. Finally, k sized max-heap is the closed k stars.


Total complexity: 3nlogn + 6kn + 5klogk.
Considering k << n, we have: O(nlogn).