Change priorityQueue to max priorityqueue

I have priority queue in Java of Integers:

 PriorityQueue<Integer> pq= new PriorityQueue<Integer>();

When I call pq.poll() I get the minimum element.

Question: how to change the code to get the maximum element?

How about like this:

PriorityQueue<Integer> queue = new PriorityQueue<>(10, Collections.reverseOrder());
queue.offer(1);
queue.offer(2);
queue.offer(3);
//...

Integer val = null;
while( (val = queue.poll()) != null) {
    System.out.println(val);
}

The Collections.reverseOrder() provides a Comparator that would sort the elements in the PriorityQueue in a the oposite order to their natural order in this case.

You can use lambda expression since Java 8.

The following code will print 10, the larger.

// There is overflow problem when using simple lambda as comparator, as pointed out by Фима Гирин.
// PriorityQueue<Integer> pq = new PriorityQueue<>((x, y) -> y - x);

PriorityQueue<Integer> pq =new PriorityQueue<>((x, y) -> Integer.compare(y, x));

pq.add(10);
pq.add(5);
System.out.println(pq.peek());

The lambda function will take two Integers as input parameters, subtract them from each other, and return the arithmetic result. The lambda function implements the Functional Interface, Comparator<T>. (This is used in place, as opposed to an anonymous class or a discrete implementation.)

In Java 8+ you can create a max priority queue via one of these methods:

Method 1:

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

Method 2:

PriorityQueue<Integer> maxPQ = new PriorityQueue<>((a,b) -> b - a);

Method 3:

PriorityQueue<Integer> maxPQ = new PriorityQueue<>((a,b) -> b.compareTo(a));

You can provide a custom Comparator object that ranks elements in the reverse order:

PriorityQueue<Integer> pq = new PriorityQueue<Integer>(defaultSize, new Comparator<Integer>() {
    public int compare(Integer lhs, Integer rhs) {
        if (lhs < rhs) return +1;
        if (lhs.equals(rhs)) return 0;
        return -1;
    }
});

Now, the priority queue will reverse all its comparisons, so you will get the maximum element rather than the minimum element.

Hope this helps!

PriorityQueue<Integer> pq = new PriorityQueue<Integer> (
  new Comparator<Integer> () {
    public int compare(Integer a, Integer b) {
       return b - a;
    }
  }
);

Change priorityQueue to max priorityqueue

Related

Recent Posts