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?

Parallax

I think you should use the constructor that receives a comparator for that. Use the Collections.reverseOrder to obtain a reversed comparator. – Gnomon

you need to pass a comparator. see #683541 – Bornie

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.

Gnomon

Collections.reverseOrder() is also overloaded to take a comparator, so it also works if you compare custom objects. – Adelaidaadelaide

Java 8's PriorityQueue has a new constructor, which just takes comparator as an argument PriorityQueue(Comparator<? super E> comparator). – Zinnes

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

Uranometry

lambda function, names its input parameters x and y and returns y-x, which is basically what the int comparator class does except it returns x-y – Arst

The comparator like (x, y) -> y - x may be not appropriate for long integers due to overflow. For example, numbers y = Integer.MIN_VALUE and x = 5 results in positive number. It is better to use new PriorityQueue<>((x, y) -> Integer.compare(y, x)). Though, the better solution is given by @Edwin Dalorzo to use Collections.reverseOrder(). – Bucella

@ФимаГирин That's true. -2147483648 - 1 becomes 2147483647 – Uranometry

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

Hic

Be careful on 2nd method, unless there is some constraints on the Integer numbers, it is best to stay away from this method. Try and what happened when you insert -2147483648 and 1 to the queue. It will make -2147483648 as the root as supposed to 1. – Protractile

Another option for comparator (u, v) -> Integer.compare(v, u). – Shorn

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!

Salgado

maybe for a max priority q the lhs<rhs returs +1; what you wrote here is minimum q after my testing – Emboly

For reverse printing, that is if the highest elements are to be printed first in a priority queue, it should be if (rhs < lhs) return +1; if (rhs > lhs) return -1; – Wardle

@Diksha I believe the code I have is equivalent to what you're posting. I've just used the greater-than relation rather than less-than. – Salgado

actually, my mistake.. I meant it should be like this: if (lhs < rhs) return +1; if (lhs > rhs) return -1; – Wardle

I had to use public int compare(Integer lhs, Integer rhs) in order get rid of the error message "cannot implement compare(T,T) in Comparator" – Alcaic

@ShrikantPrabhu Good catch - that's now fixed! – Salgado

Just return rhs - lhs should do. – Aconite

@Aconite I think (?) that you need to watch out for integer overflow with that approach in some cases. But perhaps I’m mistaken? – Salgado

@Salgado good point, as I saw you explicit passed <Integer> as the type, I assumed that should not happen in the change I suggested. – Aconite

Answer 5

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

Muraida

What is the problem ? – Bane

This is perfect and does exactly what was asked by turning a min heap into a max heap. – Wickedness

using b-a can cause overflow so should avoid using it and should use Collections.reverseOrder(); as a comparator or replace b-a with Integer.compare(a,b); which has been added in Java 8 – Forborne

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

Falcon

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

Paraph

Probably would be easier just returning n1.compareTo(n2) * (-1) or n2.compareTo(n1) in compare method – Deponent

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

Chirm

Answer 9

This can be achieved by using

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

Lard

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

Conduit

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.

Dunton

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.

Jeneejenei

404. That’s an error. The requested URL /git/javadoc/com/google/common/collect/MinMaxPriorityQueue.html was not found on this server. Seems like the link is broken, need to get the detailed info next time. – Autointoxication

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

Thermoscope

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

Emboly

For reverse printing, that is if the highest elements are to be printed first in a priority queue, it should be if (rhs < lhs) return +1; if (rhs > lhs) return -1; – Wardle

You can edit it if you like. I have no time to confirm what you wrote. In my setup what i wrote was correct – Emboly

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

Bushcraft

Or simply (a,b) -> b - a. – Kathrynekathy

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.

Undershot

Answer 17

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

Nevile

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 ]

Icebreaker

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.

Mejias

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.

Pembroke