Changing Java PriorityQueue to a Max PQ

Question

The Priority Queue implementation in the Java standard library appears to be a min Priority Queue which I found somewhat confusing. In order to turn it into a max one I created a custom comparator object.

Comparator<Integer> cmp = new Comparator<Integer>()
{
    public int compare( Integer x, Integer y )
    {
        return y - x;
    }
};

I was wondering if there was a more elegant solution. Essentially I wan't a generic priority queue that could be used to implement Dijkstras etc. I didn't even realise there would be ones which operated in reverse :/

score 35 · Answer 1 · answered Sep 30 '12 at 22:47

35

Here is a code snippet using Collections.reverseOrder()-

    PriorityQueue<Integer> maxPQ = new PriorityQueue<Integer>(20,Collections.reverseOrder());

You also need to provide the initial capacity of the Priority Queue (20 here) along with the Comparator.

answered Sep 30 '12 at 22:47

pyrometer

890
1
8
17

6

Java 8 adds a constructor that takes just a Comparator (https://docs.oracle.com/javase/8/docs/api/java/util/PriorityQueue.html), so if you're using Java 8 you don't have to provide the initial capacity. – tsleyson May 03 '16 at 22:05

score 24 · Accepted Answer · edited Dec 01 '11 at 22:25

24

Use Java's Collections.reverseOrder() comparator.

Java Reference

edited Dec 01 '11 at 22:25

Christian Specht

35,843
15
128
182

answered Dec 01 '11 at 22:15

Suman Chitturi

356
2
4

score 6 · Answer 3 · answered Apr 02 '12 at 04:57

Not sure what you mean by elegant but when I want a PQ implemented like a MaxHeap (used in Dijkstra's) I just use an inline comparator constructor.

PriorityQueue<Integer> PQ= new PriorityQueue<Integer>(20, new Comparator<Integer>(){
            public int compare(Integer o1, Integer o2){
                return o2 - o1;
            }
        });

It's simple enough for anytime I'm looking for something simple and only want to use the Comparator once.

score 0 · Answer 4 · answered Sep 14 '10 at 10:33

If you have an existing comparator you could create a generic inversing comparator.

public class InverseComparator<T> implements Comparator<T> {
    private final Comparator<T> delegate;

    public InverseComparator(Comparator<T> delegate) {
        this.delegate = delegate;
    }

    public int compare(T x, T y) {
        return delegate(y, x);
    }
}

Changing Java PriorityQueue to a Max PQ

4 Answers4

Linked