[Haskell-cafe] Re: k-minima in Haskell

ajb@spamcop.net wrote:

Quoting apfelmus :

...

You mean O(k * log n + n) of course.

Erm, yes. You can do it in an imperative language by building a heap in O(n) time followed by removing k elements, in O(k log n) time.

Ah, sorry, there are indeed to variants not comparable to each other. Threading a heap of k elements over the entire list needs O(n log k + k) time and putting all of the list into a heap takes O(k log n + n) time. For say k = O(sqrt(n)), the former is slower than the latter but it only needs to keep O(k) list elements in memory. I think that every k-minima algorithm of the form take k . sort has to keep all list elements in memory: the sort may not throw away anything because it cannot know how many elements are requested. Regards, apfelmus