Which is the appropriate data structure?

Question

I need a Java data structure that has:

• fast (O(1)) insertion
• fast removal
• fast (O(1)) max() function

What's the best data structure to use?

HashMap would almost work, but using java.util.Collections.max() is at least O(n) in the size of the map. TreeMap's insertion and removal are too slow.

Any thoughts?

Answer 1

O(1) insertion and O(1) max() are mutually exclusive together with the fast removal point.

A O(1) insertion collection won't have O(1) max as the collection is unsorted. A O(1) max collection has to be sorted, thus the insert is O(n). You'll have to bite the bullet and choose between the two. In both cases however, the removal should be equally fast.

If you can live with slow removal, you could have a variable saving the current highest element, compare on insert with that variable, max and insert should be O(1) then. Removal will be O(n) then though, as you have to find a new highest element in the cases where the removed element was the highest.

Answer 2

If you can have O(log n) insertion and removal, you can have O(1) max value with a TreeSet or a PriorityQueue. O(log n) is pretty good for most applications.