When does a heap beat sorting?

For k from 1 to n minus 1, keep a max-heap of the k smallest values seen so far. For each new value, compare it with the heap top; replace the top only when the new value is smaller. This takes O(n log k) time and O(k) extra space. Sorting all values takes O(n log n), and is often simpler when the full order is needed.