我在Java中有一个整数的优先队列:
PriorityQueue<Integer> pq= new PriorityQueue<Integer>();
当我调用pq.poll()
时,会返回最小的元素。
问题:如何更改代码以获取最大的元素?
我在Java中有一个整数的优先队列:
PriorityQueue<Integer> pq= new PriorityQueue<Integer>();
当我调用pq.poll()
时,会返回最小的元素。
问题:如何更改代码以获取最大的元素?
这样怎么样:
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);
}
Collections.reverseOrder()
提供了一个Comparator
,它会将PriorityQueue
中的元素按照与其自然顺序相反的顺序进行排序。
Collections.reverseOrder()
还被重载了,可以接受一个比较器,因此它也适用于比较自定义对象。 - flying sheepPriorityQueue(Comparator<? super E> comparator)
。 - abhisheknirmal自Java 8以来,您可以使用lambda表达式。
以下代码将打印出10,其中较大的数字。
// 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());
这个 Lambda 函数将以两个整数作为输入参数,相互相减并返回算术结果。这个 Lambda 函数实现了函数式接口 Comparator<T>
。(与匿名类或离散实现不同,该函数可用于替代这些实现方法。)
(x, y) -> y - x
这样的比较器可能由于溢出而不适用于长整型。例如,当y=Integer.MIN_VALUE且x=5时,结果为正数。更好的解决方案是使用new PriorityQueue<>((x, y) -> Integer.compare(y, x))
。不过,@Edwin Dalorzo提供了更好的解决方案,即使用Collections.reverseOrder()
。 - Фима Гирин在Java 8及以上版本中,您可以通过以下其中一种方法创建最大优先级队列:
方法1:
PriorityQueue<Integer> maxPQ = new PriorityQueue<>(Collections.reverseOrder());
方法二:
PriorityQueue<Integer> maxPQ = new PriorityQueue<>((a,b) -> b - a);
方法三:
PriorityQueue<Integer> maxPQ = new PriorityQueue<>((a,b) -> b.compareTo(a));
(u, v) -> Integer.compare(v, u)
。 - Muhammad Khuzaima Umair您可以提供一个自定义的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;
}
});
现在,优先队列将反转所有比较操作,因此您将获得最大元素而不是最小元素。
希望这能帮到你!
if (rhs < lhs) return +1;
if (rhs > lhs) return -1;
。 - Tiaif (lhs < rhs) return +1; if (lhs > rhs) return -1;
。 - TiaPriorityQueue<Integer> pq = new PriorityQueue<Integer> (
new Comparator<Integer> () {
public int compare(Integer a, Integer b) {
return b - a;
}
}
);
b-a
可能会导致 溢出
,因此应避免使用它,并应使用 Collections.reverseOrder();
作为比较器,或者将 b-a
替换为在 Java 8
中添加的 Integer.compare(a,b);
。 - Yug Singh优先级队列的元素按照它们的自然顺序排序,或者按照在队列构造时提供的比较器进行排序。
比较器应该覆盖compare方法。
int compare(T o1, T o2)
默认比较方法将返回负整数、零或正整数,如果第一个参数小于、等于或大于第二个参数。
Java提供的默认优先队列是最小堆,如果想要一个最大堆,请使用以下代码:
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());
}
}
}
参考:https://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html#comparator()
这个链接提供了PriorityQueue的comparator()方法的文档。该方法返回队列使用的比较器,如果没有指定,则为null。使用比较器可以控制PriorityQueue中元素的顺序。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;
}
}
compare
方法中,直接返回n1.compareTo(n2) * (-1)
或者n2.compareTo(n1)
可能会更容易。 - jschermanPriorityQueue<Integer> pq = new PriorityQueue<Integer>(Collections.reverseOrder());
在Java 8中,可以通过以下代码实现。引入了一个仅接受比较器的构造函数。
PriorityQueue<Integer> maxPriorityQ = new PriorityQueue<Integer>(Collections.reverseOrder());
将PriorityQueue转换为MAX PriorityQueue 方法1: Queue pq = new PriorityQueue<>(Collections.reverseOrder()); 方法2: Queue pq1 = new PriorityQueue<>((a, b) -> b - a); 让我们看几个例子:
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
*/
}
}
让我们来看一个著名的面试问题:使用优先队列查找数组中第K大元素。
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
*/
}
}
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
*/
}
}