`Bag.top(bottom)Occurrences` about eclipse-collections HOT 4 OPEN

Sorry that was a typo, I forgot the logarithm.

One implementation is to keep a min heap of fixed size k. Insert every (item, count) pair into it and remove the minimum whenever the heap size exceeds k. Inserting and removing in this heap is O(log k) since its fixed to size k. Handling ties is tricky in this implementation but can be done.

Another implementation is to heapify all items into a max heap, and then pop the max until we're done. This approach makes it easier to handle ties, since they come at the end. Heapify is O(n). Popping the max from a max heap is O(log n). So overall, this approach is O(k log n).

from eclipse-collections.

the topOccurrences() method has an inefficient implementation that ought to be optimized. The current implementation sorts, as you said, making it O(n log n). The selection algorithm is O(n) and sorting would take O(k log k) in the absence of ties.

from eclipse-collections.

I took a look at Python's most_common and it takes the front element from a heap k times, making it O(n * k). This is a nice compromise in that it's faster than our implementation, but still pretty easy to implement.

from eclipse-collections.

I took a look at Python's most_common and it takes the front element from a heap k times, making it O(n * k). This is a nice compromise in that it's faster than our implementation, but still pretty easy to implement.

That's only decent if k < log(n). For k near n, it's impossible to do better than sorting (simply because the result has to be sorted) and we don't want O(n^2). So the algorithm needs to be smart based on k vs n.

I wonder how bad it would be to stuff the first k elements in a tree, then remove the worst one as new ones are added (the tree would have to be a list at each node to contain the equals).

from eclipse-collections.