How to get all in constant time?

We are planning to design a system where following operations are supported.

Increment("foo"): Increase the count of key 'foo'

Decrement("bar"): Decrease the count of key 'bar'

getMin():  Return the key which has minimum count

getMax():  Return the key which has maximum count


The catch is all operations should be in $O(1)$ time.

• Fibonacci heaps support all your operations in $O(1)$ amortized running time (you need to maintain two heaps, one for getMin and one for getMax). The Wikipedia page describes several other heaps which have $O(1)$ worst case running time for all these operations. – Yuval Filmus Sep 10 '18 at 6:49
• Without something not bounded by a constant, there is no point in asymptotic analysis. Be explicit, don't make your readers guess there can be $n$ keys. – greybeard Sep 12 '18 at 8:16

If your keys are strings, you can use a prefix tree mapping keys to values. In this way each operation can be implemented in $O(h)$ time, where $h$ is the length of the key, which means it is $O(1)$ to the size of the collection.
I don't think you can get better complexity than $O(h)$ for arbitrary sized keys as you need $O(h)$ time to output the key anyway.