A heap based problem
You don't need to put all numbers encountered in the heap. Never let your heap grow in size more than $k$. Keep a min heap. Now, if at some point of time heap has size $ &lt; k$, then push the number encountered ( say $i$ ) into the heap. If heap is full and the number $i$ is greater than top element of heap ( say $top$ ) , pop the $top$ and insert $i$ into heap. At the end all the numbers in the heap are your desired $k$ numbers. Each operation takes $O(logk)$ steps ( as heap size is always $ \le k$ ). And there are $n$ steps so $O(nlogk)$.