CODEWITHSUNDEEP
javacollectionsqueuepriority-queue
Cratylus
Cratylus

Reputation: 54094

Max-priority Queue in the Java's standard Collections. Is there one?

I need a Max-Priority Queue data structure.

Looking in Java's Priority Queue I noticed that it is a Min-Priority Queue.

From javadoc:

The head of this queue is the least element with respect to the specified ordering

I saw that there is the option to provide a custom Comparator and looking at some posts some suggest to use one and do the reverse comparison to achieve the result of a Max Priority Queue.
This seems to me though a "ugly-hack" and perhaps not intuitive.

Is this the only way to have a Max-Priority Queue from the Java's standard collection?
Is there a more appropriate object I am missing? (E.g. a while back I didn't realize that Stack was replaced by a Deque...my bad)

Upvotes: 0

Views: 1507

Answers (2)

Tudor
Tudor

Reputation: 62459

It is not a Min-Heap. You are misinterpreting this part:

The head of this queue is the least element with respect to the specified ordering.

The emphasis is on specified ordering. That can be anything, including a descending comparison. Providing your own comparator is how it's supposed to be used and it's definitely not an "ugly hack".

Right at the beginning:

This queue orders elements according to an order specified at construction time, which is specified either according to their natural order (see Comparable), or according to a Comparator, depending on which constructor is used.

This clearly states that providing your own comparator is expected behavior.

Upvotes: 2

JB Nizet
JB Nizet

Reputation: 692073

AFAIK, yes, it's the best way to have what you want. I really don't see how it's an ugly hack. There is no point of providing two different classes if just one is sufficient. If we followed your reasoning, we would have a MinTreeSet and a MaxTreeSet, a MinTreeMap and a MaxTreeMap, etc., all doining exactly the same thing. It's a classical use of the strategy pattern.

Just use Collections.reverseOrder() to get a comparator that compares in the reverse order of the natural ordering.

Upvotes: 7

Related Questions