Mixing
Change priorityQueue to max priorityqueue
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.
pq.poll()
Question: how to change the code to get the maximum element?
you need to pass a comparator. see stackoverflow.com/questions/683041/…
– DarthVader
Jun 12 '12 at 19:08
10 Answers
10
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.
Collections.reverseOrder()
Comparator
PriorityQueue
Collections.reverseOrder() is also overloaded to take a comparator, so it also works if you compare custom objects.– flying sheep
Jul 4 '13 at 18:11
Collections.reverseOrder()
Java 8's PriorityQueue has a new constructor, which just takes comparator as an argument
PriorityQueue(Comparator<? super E> comparator).– nickspol
May 12 '16 at 20:48
PriorityQueue(Comparator<? super E> comparator)
You can use lambda expression since Java 8.
The following code will print 10, the larger.
PriorityQueue<Integer> pq = new PriorityQueue<>((x, y) -> 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.)
Comparator<T>
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
– Edi Bice
Jun 22 '17 at 19:44
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().– Фима Гирин
Jan 20 at 21:12
(x, y) -> y - x
new PriorityQueue<>((x, y) -> Integer.compare(y, x))
Collections.reverseOrder()
@ФимаГирин That's true. -2147483648 - 1 becomes 2147483647
– Guangtong Shen
Jan 22 at 20:50
You can provide a custom Comparator object that ranks in the reverse order:
Comparator
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!
Is there a constructor that receives only a Comparator as parameter? Because I can only see one that receives a initial capacity and a comparator
– Edwin Dalorzo
Jun 12 '12 at 19:12
@EdwinDalorzo- Whoops, forgot about that parameter. Thanks for spotting that, and fixed.
– templatetypedef
Jun 12 '12 at 19:13
maybe for a max priority q the lhs<rhs returs +1; what you wrote here is minimum q after my testing
– sivi
Mar 3 '15 at 20:26
actually, my mistake.. I meant it should be like this:
if (lhs < rhs) return +1; if (lhs > rhs) return -1;– Tia
Feb 23 '16 at 18:40
if (lhs < rhs) return +1; if (lhs > rhs) return -1;
@ShrikantPrabhu Good catch - that's now fixed!
– templatetypedef
May 29 at 18:11
PriorityQueue<Integer> pq = new PriorityQueue<Integer> (
new Comparator<Integer> () {
public int compare(Integer a, Integer b) {
return b - a;
}
}
);
What is the problem ?
– CMedina
Mar 11 '16 at 18:01
This is perfect and does exactly what was asked by turning a min heap into a max heap.
– Kamran
Feb 25 at 21:34
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()
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
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.
MinMaxPriorityQueue
poll()
pollLast()
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.
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;
}
});
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;– Tia
Feb 10 '16 at 19:11
if (rhs < lhs) return +1;
You can edit it if you like. I have no time to confirm what you wrote. In my setup what i wrote was correct
– sivi
Feb 10 '16 at 22:02
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.
By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.
I think you should use the constructor that receives a comparator for that. Use the Collections.reverseOrder to obtain a reversed comparator.
– Edwin Dalorzo
Jun 12 '12 at 19:08