将优先队列改为最大优先队列。

Question

我在Java中有一个整数的优先队列：

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

当我调用pq.poll()时，会返回最小的元素。

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

- Borut Flis

---

我认为你应该使用接收比较器的构造函数来实现。可以使用Collections.reverseOrder获取一个反向比较器。 - Edwin Dalorzo

你需要传递一个比较器。请参阅https://dev59.com/zXRB5IYBdhLWcg3wN1EQ。 - DarthVader

Answer 1

这样怎么样：

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中的元素按照与其自然顺序相反的顺序进行排序。

- Edwin Dalorzo

---

Collections.reverseOrder() 还被重载了，可以接受一个比较器，因此它也适用于比较自定义对象。 - flying sheep

Java 8的PriorityQueue有一个新的构造函数，只接受比较器作为参数PriorityQueue(Comparator<? super E> comparator)。 - abhisheknirmal

Answer 2

自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>。（与匿名类或离散实现不同，该函数可用于替代这些实现方法。）

- Guangtong Shen

---

lambda函数，命名其输入参数为x和y，并返回y-x，这基本上就是int比较器类所做的，只不过它返回的是x-y。 - Edi Bice

像(x, y) -> y - x这样的比较器可能由于溢出而不适用于长整型。例如，当y=Integer.MIN_VALUE且x=5时，结果为正数。更好的解决方案是使用new PriorityQueue<>((x, y) -> Integer.compare(y, x))。不过，@Edwin Dalorzo提供了更好的解决方案，即使用Collections.reverseOrder()。 - Фима Гирин

@ФимаГирин 那是真的。 -2147483648 - 1 变成了 2147483647。 - Guangtong Shen

Answer 3

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

- apadana

---

第二种方法需要小心，除非整数数字有一些限制，否则最好远离这种方法。尝试将-2147483648和1插入队列时会发生什么。它会将-2147483648作为根而不是1。 - johnsam

另一种比较器的选项是 (u, v) -> Integer.compare(v, u)。 - Muhammad Khuzaima Umair

Answer 4

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

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

希望这能帮到你！

- templatetypedef

---

或许对于最大优先队列，当lhs<rhs时返回+1；你所写的是在我的测试中得出的最小优先队列。 - sivi

对于反向打印，也就是如果要先打印优先队列中最高的元素，应该使用 if (rhs < lhs) return +1; if (rhs > lhs) return -1;。 - Tia

@Diksha 我相信我所拥有的代码与你发布的代码是等效的。我只是使用了大于关系而不是小于关系。 - templatetypedef

实际上，我搞错了...我的意思是应该像这样：if (lhs < rhs) return +1; if (lhs > rhs) return -1;。 - Tia

@ShrikantPrabhu 很好的发现 - 现在已经修复了！ - templatetypedef

Answer 5

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

- Varun Juneja

---

什么问题？ - CMedina

这是完美的，正如所要求的那样，将最小堆变成了最大堆。 - Kamran

使用 b-a 可能会导致 溢出，因此应避免使用它，并应使用 Collections.reverseOrder(); 作为比较器，或者将 b-a 替换为在 Java 8 中添加的 Integer.compare(a,b);。 - Yug Singh

Answer 6

优先级队列的元素按照它们的自然顺序排序，或者按照在队列构造时提供的比较器进行排序。

比较器应该覆盖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中元素的顺序。

- rohan

Answer 7

我们可以通过创建实现 Comparator 接口并覆盖其 compare 方法的 CustomComparator 类来完成这一点。以下是相应代码:

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

- Hardik Vagadia

---

在compare方法中，直接返回n1.compareTo(n2) * (-1)或者n2.compareTo(n1)可能会更容易。 - jscherman

Answer 8

这可以通过使用来实现。

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

- Ajinkya_M

Answer 9

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

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

- Anshu Shekhar

Answer 10

将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

         */
    }
}

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

- Soudipta Dutta