topN using a heap

[Timon Gehr via Digitalmars-d]

On 01/16/2016 10:28 PM, Ivan Kazmenko wrote:
> On Saturday, 16 January 2016 at 15:25:50 UTC, Andrei Alexandrescu wrote:
>> ...
>
> To summarize:
> For k<<n we have O(n) average case and O(n log k) worst case.
> For k~n we have O(n log n) as HeapSort.
>

The implementation falls back to topNHeap whenever k is within the first 
or last ~n/8 elements and therefore is Ω(n log n) on average.