Change priorityQueue to max priorityqueue

Question

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?

Answer 1

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.

Answer 2

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.)

Answer 3

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)); 

Answer 4

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!

Answer 5

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

Answer 6

The elements of the priority queue are ordered according to their natural ordering, or by a Comparator provided at queue construction time.

The Comparator should override the compare method.

int compare(T o1, T o2)

Default compare method returns a negative integer, zero, or a positive integer as the first argument is less than, equal to, or greater than the second.

The Default PriorityQueue provided by Java is Min-Heap, If you want a max heap following is the code

public class Sample {
    public static void main(String[] args) {
        PriorityQueue<Integer> q = new PriorityQueue<Integer>(new Comparator<Integer>() {

            public int compare(Integer lhs, Integer rhs) {
                if(lhs<rhs) return +1;
                if(lhs>rhs) return -1;
                return 0;
            }
        });
        q.add(13);
        q.add(4);q.add(14);q.add(-4);q.add(1);
        while (!q.isEmpty()) {
            System.out.println(q.poll());
        }
    }

}

Reference :https://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html#comparator()

Answer 7

We can do this by creating our CustomComparator class that implements Comparator interface and overriding its compare method. Below is the code for the same :

import java.util.PriorityQueue;
import java.util.Comparator;
public class Main
{
    public static void main(String[] args) {
        PriorityQueue<Integer> nums = new PriorityQueue<>(new CustomComparator());
        nums.offer(21);
        nums.offer(1);
        nums.offer(8);
        nums.offer(2);
        nums.offer(-4);
        System.out.println(nums.peek());
    }
}
class CustomComparator implements Comparator<Integer>{
    @Override
    public int compare(Integer n1, Integer n2){
        int val = n1.compareTo(n2);
        if(val > 0)
           return -1;
        else if(val < 0)
            return 1;
        else
            return 0;
    }
}

Answer 8

This can be achieved by the below code in Java 8 which has introduced a constructor which only takes a comparator.

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

Answer 9

This can be achieved by using

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

Answer 10

Here is a sample Max-Heap in Java :

PriorityQueue<Integer> pq1= new PriorityQueue<Integer>(10, new Comparator<Integer>() {
public int compare(Integer x, Integer y) {
if (x < y) return 1;
if (x > y) return -1;
return 0;
}
});
pq1.add(5);
pq1.add(10);
pq1.add(-1);
System.out.println("Peek: "+pq1.peek());

The output will be 10

Answer 11

Change PriorityQueue to MAX PriorityQueue Method 1 : Queue pq = new PriorityQueue<>(Collections.reverseOrder()); Method 2 : Queue pq1 = new PriorityQueue<>((a, b) -> b - a); Let's look at few Examples:

public class Example1 {
    public static void main(String[] args) {

        List<Integer> ints = Arrays.asList(222, 555, 666, 333, 111, 888, 777, 444);
        Queue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        pq.addAll(ints);
        System.out.println("Priority Queue => " + pq);
        System.out.println("Max element in the list => " + pq.peek());
        System.out.println("......................");
        // another way
        Queue<Integer> pq1 = new PriorityQueue<>((a, b) -> b - a);
        pq1.addAll(ints);
        System.out.println("Priority Queue => " + pq1);
        System.out.println("Max element in the list => " + pq1.peek());
        /* OUTPUT
          Priority Queue => [888, 444, 777, 333, 111, 555, 666, 222]
          Max element in the list => 888
          ......................
           Priority Queue => [888, 444, 777, 333, 111, 555, 666, 222]
           Max element in the list => 888

         */


    }
}

Let's take a famous interview Problem : Kth Largest Element in an Array using PriorityQueue

public class KthLargestElement_1{
    public static void main(String[] args) {

        List<Integer> ints = Arrays.asList(222, 555, 666, 333, 111, 888, 777, 444);
        int k = 3;
        Queue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        pq.addAll(ints);
        System.out.println("Priority Queue => " + pq);
        System.out.println("Max element in the list => " + pq.peek());
        while (--k > 0) {
            pq.poll();
        } // while
        System.out.println("Third largest => " + pq.peek());
/*
 Priority Queue => [888, 444, 777, 333, 111, 555, 666, 222]
Max element in the list => 888
Third largest => 666

 */
    }
}

Another way :

public class KthLargestElement_2 {
    public static void main(String[] args) {
        List<Integer> ints = Arrays.asList(222, 555, 666, 333, 111, 888, 777, 444);
        int k = 3;

        Queue<Integer> pq1 = new PriorityQueue<>((a, b) -> b - a);
        pq1.addAll(ints);
        System.out.println("Priority Queue => " + pq1);
        System.out.println("Max element in the list => " + pq1.peek());
        while (--k > 0) {
            pq1.poll();
        } // while
        System.out.println("Third largest => " + pq1.peek());
        /*
          Priority Queue => [888, 444, 777, 333, 111, 555, 666, 222] 
          Max element in the list => 888 
          Third largest => 666

         */
    }
}

As we can see, both are giving the same result.

Answer 12

You can use MinMaxPriorityQueue (it's a part of the Guava library): here's the documentation. Instead of poll(), you need to call the pollLast() method.

Answer 13

I have mentioned 5 ways to achieve :

1. Using compareTo() Method

   PriorityQueue<Integer> pq = new PriorityQueue<>((o1, o2) -> o2.compareTo(o1));

2. Using compare() Method

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

3. Using Custom Comparator Method

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

    static class CustomIntegerComparator implements Comparator<Integer> {

        @Override
        public int compare(Integer o1, Integer o2) {
            return o1 < o2 ? 1 : -1;
        }
    }

4. Using Collection Method

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

5. Using Arrow(Lambda expression) Function

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

6. Using Custom Comparator Method (via Difference)

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

Answer 14

I just ran a Monte-Carlo simulation on both comparators on double heap sort min max and they both came to the same result:

These are the max comparators I have used:

(A) Collections built-in comparator

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

(B) Custom comparator

PriorityQueue<Integer> heapLow = new PriorityQueue<Integer>(new Comparator<Integer>() {
    int compare(Integer lhs, Integer rhs) {
        if (rhs > lhs) return +1;
        if (rhs < lhs) return -1;
        return 0;
    }
});

Answer 15

Using lamda, just multiple the result with -1 to get max priority queue.

PriorityQueue<> q = new PriorityQueue<Integer>(
                       (a,b) ->  -1 * Integer.compare(a, b)
                    );

Answer 16

You can try something like:

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

Which works for any other base comparison function you might have.

Answer 17

PriorityQueue<Integer> lowers = new PriorityQueue<>((o1, o2) -> -1 * o1.compareTo(o2));

Answer 18

• Simple way to Reverse PriorityQueue using Collections.reverseOrder() in java.

-> I have the PriorityQueue:(like:)

    PriorityQueue<String> pQueue = new PriorityQueue<>();
    
    pQueue.add("Honda");
    pQueue.add("Passion");
    pQueue.add("Heroni");
    pQueue.add("Ola");

-> Create New PriorityQueue for Reverse array Store.

  PriorityQueue<String> pRqueue = new 
              PriorityQueue<String>(pQueue.size(), Collections.reverseOrder());

-> in the Syntex pQueue.size() is the array which is already Declared. so, give here only the size.

-> add elements of old queue into new Queue:

  pRqueue.addAll(pQueue);

-> and now print the queue. and Output is shown Below:

    Queue Element:[ Heroni, Ola, Honda, Passion ]
    Reverese PriorityQueue Element:[ Passion, Ola, Honda, Heroni ]

☻♥ Done. Keep Code.

Answer 19

You can try pushing elements with reverse sign. Eg: To add a=2 & b=5 and then poll b=5.

PriorityQueue<Integer>  pq = new PriorityQueue<>();
pq.add(-a);
pq.add(-b);
System.out.print(-pq.poll());

Once you poll the head of the queue, reverse the sign for your usage. This will print 5 (larger element). Can be used in naive implementations. Definitely not a reliable fix. I don't recommend it.

Answer 20

You can refer to the other answers given here. If you want a very simple hack for this, just revert the sign of the number. Suppose I want to enter 5 and 10 to the queue,

PriorityQueue<Integer> pq= new PriorityQueue<Integer>();
pq.add(-5);
pr.add(-10);

Since Priority Queue by default implements min heap in Java you can use this logic to implement max heap.