topN using a heap
Andrei Alexandrescu via Digitalmars-d
digitalmars-d at puremagic.com
Sun Jan 17 17:38:16 PST 2016
On 1/17/16 8:07 PM, deadalnix wrote:
> A common way to do it is to go quicksort, but only recurse on one side
> of the set. That should give log(n)^2 complexity on average.
Yah, that's quickselect (which this work started from). It's linear, and
you can't get top n in sublinear time because you need to look at all
elements. -- Andrei
More information about the Digitalmars-d
mailing list