My initial though was the simple approach: calculate the distance between the source and each of the other stars, and sort the other star list on this distance. This results in an O(nlogn) algorithm which is the best a sort on this type of randomized data. But there is a better way: The key is we don't need to sort all the list, we are just looking to get the closest N elements. The algorithm is as follows:

Code: Select all

```
1. create a MAX heap of size N
2. add the first N stars from the list to the heap, based on a distance comparator from the source star.
3. for the remaining stars in the list:
1. if the distance to that star is less than the top of the heap, remove the top and add this star.
4. get all the element in the heap for the result.
```

Code: Select all

```
public List<Star> closest(List<Star> stars, int n) {
PriorityQueue<Pair<Star,Double>> heap = new PriorityQueue<>(n,
(x1, x2) -> x2.getSecond().compareTo(x1.getSecond()));
for (int i =0;i<n;i++) {
heap.add(new Pair<>(stars.get(i), distance(stars.get(i))));
}
for(int i=n;i<stars.size();i++) {
if(stars.get(i) == this) continue;;
double distance = distance(stars.get(i));
if (distance < heap.peek().getSecond()) {
heap.poll();
heap.add(new Pair<>(stars.get(i), distance));
}
}
return heap.stream().map(Pair::getFirst).collect(toList());
}
```