Java priority queue

Question

Java's priority queue is a data structure with O(log n) complexity for put (insertion) and O(log n) for poll (retrieval and removal of the min element).

C++ STL's multimap has the same functionality but O(1) complexity for retrieval and removal of the min element (begin and erase). Is there an equivalent in Java ?

Answer 1

Try the Apache Commons Collections.

MultiHashMap and MultiValueMap (linked from that page) actually implement the interface.

There's actually a Priority Queue in there too, but it's depreciated in favour of the buffer package.

Answer 2

Google Collections provides a Multimap implementation. Specifically, a TreeMultimap can use comparators to sort based on either keys, values or both.

Answer 3

std:multimap will be a tree structure, which means that add and remove together will be O(log n).

Answer 4

First, I'd check that C++'s multimap actually does give O(1) for removing the min element. The most common structures for sotred maps/priority queues are tree structures in which querying the min element has O(1) complexity, but removing it is O(log n).

That said, I think that a skip list (as implemented by Java's ConcurrentSkipListMap) might give you O(1) for removal of the minimum element, but I'm not absolutely sure. One of the problems when assessing performance of ConcurrentSkipListMap is that traversal operations "tidy up" markers left by previous deletions. So the complexity of an operation can actually depend on what the previous operations were. (On the other hand, at some level, that's true of pretty much any algorithm: whether some data is in the CPU cache can depend on whether a previous operation put it there...)

P.S. Forgot to say: look at ConcurrentSkipListMap.pollFirstEntry().