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

ajb at spamcop.net ajb at spamcop.net
Thu Apr 12 23:37:41 EDT 2007


G'day all.

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.

Cheers,
Andrew Bromage


More information about the Haskell-Cafe mailing list