how to get top N distinct elements from range?

[Chris Cain]

On Friday, 8 March 2013 at 15:04:32 UTC, Ivan Kazmenko wrote:
>
> For a finite range, you can iterate over the range while 
> maintaining a collection of the top n elements and discarding 
> duplicates as you find them.  For example, using a RedBlackTree 
> as the collection, you will get O(log(n) * range.length) total 
> time and O(n) total memory used.  If n is small (on the order 
> of 10s), an array will suffice, resulting in O(n * 
> range.length) total time but with lower constant factor.

You can also use an array if you use a BinaryHeap. If you use a 
heap then it should have a much lower constant factor than a 
red-black tree so, even though they would both have O(m*log(n)) 
(where n is the number of elements you want the top of and m is 
the size of the collection) running time, a heap would be faster.