What is the best data structure for keeping the top n elements in sort order?

Question

I am looking for a data structure which keeps the top n elements, similar to this question, but with the added requirement of maintaining sort order. Obviously I could just sort at the end but there might be a more efficient way to do it on the fly. There will only be insertions, never removals, and then an iteration through the top n elements at the end.

This question is language agnostic but it will be in C# so an answer that uses native .NET collections is preferable.

EDIT: I should clarify that the sort order only matters at the very end when the top n elements are iterated over. Along the way as there are insertions the sort order is irrelevant as long as the top n elements are retained.

Answer 1

You'll have to give us a clue on the order of n and the number of items to be inserted.

I would think the sort order is relevant, how else will you know which elements are part of the top n? Just because you only want the top n at the end of all insertions may be creating a bias for / against structures or algorithms.

Why keep any of the items that aren't in the top n? You could use a sorted set (thinking of Python's deque) of size n+1. When adding, iterate through the list and insert the new item in the correct location in the set. When the set gets to size (n+1), each insert is followed by delete of the last item. This way you always have the top n items without growing the data structure with items that will never be retrieved.

In addition, if you keep the value of the bottom element (the last of n, call it b) then you can use that to skip the insert altogether. This limits the number of comparisons to O(1) when new item x is larger than b.