topN using a heap

[Andrei Alexandrescu via Digitalmars-d]

On 1/16/16 8:00 PM, Timon Gehr wrote:
> 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.

Correct. The pedantic approach would be to only do that when k is up to 
log(n). -- Andrei