Compute the K Closed Stars

Consider a coordinate system for the Milky Way, in which the Earth is at (0,0,0). Model stars as points, and assume distances are in light years. The Milky Way consists of approximately 10^12 stars, and their coordinates are stored in a CSV file --- one line per star and four fields per line, the first corresponding to an ID, and then three floating point numbers corresponding to the star location.

How would you compute the k stars which are closet to the Earth? You have only a few megabytes of RAM.

解题思路

使用一个有k个元素的最大堆H。

public class ClosestStars {
  public static class Star implements Comparable<Star>, Serializable {
    private double x, y, z;

    public Star(double x, double y, double z) {
      this.x = x;
      this.y = y;
      this.z = z;
    }

    public double distance() { return Math.sqrt(x * x + y * y + z * z); }

    @Override
    public int compareTo(Star rhs) {
      return Double.compare(this.distance(), rhs.distance());
    }

    @Override
    public String toString() { return "(" + x + "," + y + "," + z + ")"; }

  }


public static List<Star> findClosestKStars(int k, ObjectInputStream osin)
      throws ClassNotFoundException, IOException {
    // maxHeap to store the closest k stars seen so far.
    PriorityQueue<Star> maxHeap
        = new PriorityQueue<>(k, Collections.reverseOrder());
    try {
      while (true) {
        // Add each star to the max-heap. If the max-heap size exceeds k,
        // remove the maximum element from the max-heap.
        Star star = (Star)osin.readObject();
        maxHeap.add(star);
        if (maxHeap.size() == k + 1) {
          maxHeap.remove();
        }
      }
    } catch (EOFException e) {
      // Do nothing since the end of the stream has been reached.
    }

    List<Star> orderedStars = new ArrayList<Star>(maxHeap);
    // The only guarantee PriorityQueue makes about ordering is that the
    // maximum element comes first, so we sort orderedStars.
    Collections.sort(orderedStars);
    return orderedStars;
}


while (in.hasNextDouble()) {
   double x = in.nextDouble();
   double y = in.nextDouble();
   double z = in.nextDouble();

   Star star = new Star(x,y,z);
}