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?
218 Answers
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!
9PriorityQueue<Integer> pq = new PriorityQueue<Integer> ( new Comparator<Integer> () { public int compare(Integer a, Integer b) { return b - a; } } ); 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 :()
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; } } This can be achieved by using
PriorityQueue<Integer> pq = new PriorityQueue<Integer>(Collections.reverseOrder()); 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
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()); 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.
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.
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; } }); 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) ); 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.
PriorityQueue<Integer> lowers = new PriorityQueue<>((o1, o2) -> -1 * o1.compareTo(o2)); - 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.
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.
