topN using a heap
deadalnix via Digitalmars-d
digitalmars-d at puremagic.com
Sun Jan 17 17:42:54 PST 2016
On Monday, 18 January 2016 at 01:38:16 UTC, Andrei Alexandrescu
wrote:
> 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
Yeah; forget about me, I was dumb on that one.
More information about the Digitalmars-d
mailing list