162

我在整数 Java 中有优先级队列：

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

当我打电话时，pq.poll()我得到了最小的元素。

问题：如何更改代码以获得最大元素？

4

17 回答 17

287

像这样怎么样：

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以与它们的自然顺序相反的顺序排序。

于 2012-06-12T19:12:39.727 回答
102

从 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>. （这是就地使用的，而不是匿名类或离散实现。）

于 2016-07-09T21:10:33.063 回答
41

在 Java 8+ 中，您可以通过以下方法之一创建最大优先级队列：

方法一：

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));
于 2020-04-13T05:15:38.883 回答
31

您可以提供一个自定义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;
    }
});

现在，优先级队列将反转其所有比较，因此您将获得最大元素而不是最小元素。

希望这可以帮助！

于 2012-06-12T19:08:29.763 回答
14 
PriorityQueue<Integer> pq = new PriorityQueue<Integer> (
  new Comparator<Integer> () {
    public int compare(Integer a, Integer b) {
       return b - a;
    }
  }
);
于 2016-03-11T17:49:18.597 回答
9

优先级队列的元素根据它们的自然顺序或在队列构建时提供的比较器进行排序。

Comparator 应该覆盖 compare 方法。

int compare(T o1, T o2)

默认比较方法返回负整数、零或正整数，因为第一个参数小于、等于或大于第二个。

Java 提供的 Default PriorityQueue 是 Min-Heap，如果你想要一个 max heap 以下是代码

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

于 2016-11-15T05:19:23.677 回答
7

我们可以通过创建实现 Comparator 接口的CustomComparator类并覆盖它的 compare 方法来做到这一点。以下是相同的代码：

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;
    }
}
于 2020-08-06T05:12:55.347 回答
5

这可以通过使用来实现

PriorityQueue<Integer> pq = new PriorityQueue<Integer>(Collections.reverseOrder());
于 2019-09-16T18:10:32.487 回答
4

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

输出将是 10

于 2014-01-14T20:55:04.040 回答
4

这可以通过以下 Java 8 中的代码来实现，该代码引入了一个只接受比较器的构造函数。

PriorityQueue<Integer> maxPriorityQ = new PriorityQueue<Integer>(Collections.reverseOrder());
于 2018-07-05T01:37:52.390 回答
3

您可以使用MinMaxPriorityQueue（它是 Guava 库的一部分）： 这是文档。而不是poll()，您需要调用该pollLast()方法。

于 2013-07-24T16:36:25.373 回答
3

将 PriorityQueue 更改为 MAX PriorityQueue 方法一：Queue pq = new PriorityQueue<>(Collections.reverseOrder()); 方法二：队列 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

         */


    }
}

让我们来看一个著名的采访问题：使用 PriorityQueue 的数组中的第 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

         */
    }
}

正如我们所看到的，两者都给出了相同的结果。

于 2019-02-20T14:47:55.747 回答
2

我刚刚在双堆排序最小值最大值的两个比较器上运行了蒙特卡罗模拟，它们都得出了相同的结果：

这些是我使用的最大比较器：

(A) 集合内置比较器

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

(B) 自定义比较器

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;
    }
});
于 2015-03-04T09:16:06.633 回答
1

您可以尝试以下方法：

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

这适用于您可能拥有的任何其他基本比较功能。

于 2017-12-23T16:06:55.570 回答
1 
PriorityQueue<Integer> lowers = new PriorityQueue<>((o1, o2) -> -1 * o1.compareTo(o2));
于 2018-11-29T06:32:43.037 回答
1

使用 lamda，只需将结果与 -1 相乘即可获得最大优先级队列。

PriorityQueue<> q = new PriorityQueue<Integer>(
                       (a,b) ->  -1 * Integer.compare(a, b)
                    );
于 2020-10-21T08:03:04.097 回答
0

您可以尝试使用反向符号推送元素。例如：添加 a=2 & b=5 然后轮询 b=5。

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

一旦您轮询队列的头部，请反转您使用的符号。这将打印 5（更大的元素）。可以在幼稚的实现中使用。绝对不是可靠的解决方案。我不推荐它。

于 2016-05-18T16:03:40.983 回答