topN using a heap

Andrei Alexandrescu via Digitalmars-d digitalmars-d at puremagic.com
Sat Jan 16 18:28:34 PST 2016


On 1/16/16 9:12 PM, Andrei Alexandrescu wrote:
> On 1/16/16 4:58 PM, Ziad Hatahet via Digitalmars-d wrote:
>> On Sat, Jan 16, 2016 at 7:25 AM, Andrei Alexandrescu via Digitalmars-d
>> <digitalmars-d at puremagic.com <mailto:digitalmars-d at puremagic.com>> wrote:
>>
>>
>>     1. Organize the first 11 elements into a max heap
>>
>>
>> Why not the first 10?
>
> So you get to put the appropriate element in the 11th position. -- Andrei

To clarify this using a degenerate case: say someone calls topN(r, 0) 
i.e. find the minimum. Then you'd need a mini-heap of exactly one 
element to track the smallest element found so far. -- Andrei



More information about the Digitalmars-d mailing list