I need a data structure that always contains the nlargest elements inserted so far (in a specific order).
So, if nequal to 3, we could have the following session, in which I insert several numbers, and the contents of the container change:
[]
[1]
[1,0]
[1,0,4]
[1,4,3]
[1,4,3]
[4,3,3]
You get the idea. What is the name of the data structure? What is the best way to implement this? Or is it in some kind of library?
I am thinking of using a container that has priority_queue(delegation) for its elements, which uses inverse comparison, so it popwill remove the smallest element. Thus, the function insertfirst checks whether the new item to be inserted is larger than the smallest. If so, we discard this smallest and click on the new item.
(I have an implementation C++, but the question is still an agnostic language.)
source
share