title: 2d coordinates closest to origin
body: <p>I am looking at the following interview question : </p>
  
  <blockquote>
    <p>Given 2d coordinates , find the k points which are closest to the
    origin. Propose a data structure for storing the points and the method to get the k points. Also point out the complexity of the code.</p>
  </blockquote>
  
  <p>The solution that I have figured out is to save the 2d points in an array. For the first k points, find the distance of each point from the origin and build a max heap. For the remaining points , calculate distance from the origin , say dist. If dist is greater than the topmost element of the heap, then change topmost element of heap to dist and run the <code>heapify()</code> procedure.</p>
  
  <p>This would take <code>O(k)</code> to build the heap and <code>O((n-k)log k)</code> for <code>heapify()</code> procedure , thus the total complexity = <code>O(n log k)</code>.</p>
  
  <p>Can anyone suggest a <strong>better data structure</strong> and/or method , with a possibly better efficiency too ?</p>
  
  <p>EDIT</p>
  
  <p>Would some other data structure be beneficial here ?</p>