topN using a heap

[Timon Gehr via Digitalmars-d]

On 01/17/2016 03:09 AM, Andrei Alexandrescu wrote:
> 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
>

Ivan's analysis suggests that even something significantly larger, like 
n/log(n)² might work as an upper bound for k.
I don't think that meeting the documented runtime bounds amounts to 
pedantry. (Having linear average running time of course does not even 
imply linear expected running time, as is still written in the 
documentation.)