Data structure for efficiently returning the top-K

Question

Here's a description:

It operates like a regular map with get, put, and remove methods, but has a getTopKEntries(int k) method to get the top-K elements, sorted by the key:

For my specific use case, I'm adding, removing, and adjusting a lot of values in the structure, but at any one time there's approximately 500-1000 elements; I want to return the entries for the top 10 keys efficiently.

• I call the put and remove methods many times.
• I call the getTopKEntries method.
• I call the put and remove methods some more times.
• I call the getTopKEntries method.
• ...

I'm hoping for O(1) get, put, and remove operations, and for getTopKEntries to be dependent only on K, not on the size of the map.

So what's a data structure for efficiently returning the top-K elements of a map?

My other question is similar, but is for the case of returning all elements of a map, sorted by the key.

If it helps, both the keys and values are 4-byte integers.

Answer 1

If the sort key is a simple integer or decimal number, a trie will be quite fast. It will use up memory, and technically finding an element in a trie is O(log n). But in practice it'll be something like log₂₅₆ n, so the constant factor is very small (log₂₅₆ of 2 billion = 4).

Answer 2

I would recommend a fibonacci heap.