how to get top N distinct elements from range?

[Ivan Kazmenko]

>> 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.

My first thought was about a heap, too, but it does not allow to 
search for a duplicate in O(log(n)) as it guarantees only partial 
ordering.