what is the fastest algorithm for finding the k-maximal elements of the sequence using stl-containers

Question

I need the fastest algorithm for finding the k-maximal elements of the sequence using c++ any stl-containers. My ideas: use list or vector, sort them, get the first k-elements. in this case the number of operations equals n*log(n). n - number of elements. But I think it isn't the best one.

Answer 1

The method using std::partial_sort could be the best answer.

Also take note of std::nth_element which just get's the element at the nth position right (and partitions the sequence into 'smaller' before and 'bigger' after that nth element

So if you are really interested in just the first k elements (in no particular internal ordering) then nth_element definitely takes the biscuit

Answer 2

I think the best approach is using a vector to hold the result and building an heap in it as you traverse the input. Once the heap size reaches k you don't grow it any more (and just keep bubbling-up starting at position k-1).

When the input is finished the heap is already an answer (supposing you've not been asked to return them in order).

If however k > n/2 then it's probably better to store the ones that got bubbled out of an heap of size n - k (this assumes however that you know the number of elements n and not only k in advance).