topN using a heap

[Timon Gehr via Digitalmars-d]

On 01/19/2016 12:55 AM, Ilya wrote:
> On Monday, 18 January 2016 at 23:53:53 UTC, Timon Gehr wrote:
>> On 01/19/2016 12:50 AM, Ilya wrote:
>>> ...
>>>
>>> 1. Yes, probability of hitting the worst case repeatedly is is
>>> practically zero. But RNGs do not change this probability.
>>> 2. It is possible to build attack for our RNGs, because they are
>>> Pseudo-RNGs.
>>> --Ilya
>>
>> You also need to predict the seed. How do you do that?
>
> We can not use unpredictable seed (like system clock) in pure functions.
> --Ilya

Clearly. The point is, there already was an impure implementation of 
topN whose expected linear running time is still specified in the 
documentation. The current implementation does not fulfill this bound.