 <p>If K &lt;&lt; N, min heap is good enough because creation of heap is O(n), and if K &lt;&lt; N selecting first K items is at most O(N), otherwise you could use <a href="http://en.wikipedia.org/wiki/Selection_algorithm">selection algorithm</a> to find Kth smallest element in <code>O(n)</code> then select numbers which are smaller than found item. (Sure if some numbers are equal to Kth element select till fill <code>K</code> items).</p>