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

[apfelmus]

ajb at spamcop.net wrote:
> Quoting apfelmus <apfelmus at quantentunnel.de>: 
>> 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