topN using a heap

[deadalnix via Digitalmars-d]

On Saturday, 16 January 2016 at 15:25:50 UTC, Andrei Alexandrescu 
wrote:
> https://github.com/D-Programming-Language/phobos/pull/3934
>
> So, say you're looking for the smallest 10 elements out of 
> 100_000. The quickselect algorithm (which topN currently uses) 
> will successively partition the set in (assuming the pivot 
> choice works well) 50_000, 25_000, etc chunks all the way down 
> to finding the smallest 10.
>
> That's quite a bit of work, so 3934 uses an alternate strategy 
> for finding the smallest 10:
>
> 1. Organize the first 11 elements into a max heap
>
> 2. Scan all other elements progressively. Whenever an element 
> is found that is smaller than the largest in the heap, swap it 
> with the largest in the heap then restore the heap property.
>
> 3. At the end, swap the largest in the heap with the 10th and 
> you're done!
>
> This is very effective, and is seldom referred in the selection 
> literature. In fact, a more inefficient approach (heapify the 
> entire range) is discussed more often.
>
>
> Destroy!
>
> Andrei

A common way to do it is to go quicksort, but only recurse on one 
side of the set. That should give log(n)^2 complexity on average.