topN using a heap

[Ivan Kazmenko via Digitalmars-d]

On Sunday, 17 January 2016 at 03:26:54 UTC, Andrei Alexandrescu 
wrote:
> On 1/16/16 9:37 PM, Timon Gehr wrote:
>> Ivan's analysis suggests that even something significantly 
>> larger, like
>> n/log(n)² might work as an upper bound for k.
>
> I'm not clear on how you got to that boundary. There are a few 
> implementation details to be minded as well (quickly and 
> carefully approximating the log etc). Could you please make a 
> commented pull request against my own? Thanks! -- Andrei

The average case is O(n + (k log n log k)) for small enough k.  
So, any k below roughly n / log^2 (n) makes the second summand 
less than the first.

Of course, the constant not present in asymptotic analysis, as 
well as handling the worst case, may make this notion 
impractical.  Measure is the way :) .  The worst case is just a 
decreasing sequence, or almost decreasing if we want to play 
against branch prediction as well.