Java 中的优先级队列（最小堆）排序

Question

我在使用优先级队列时遇到了这个语句。

PriorityQueue<Integer> heap = new PriorityQueue<Integer>((n1, n2) -> n1 - n2);

在功能上我知道这是一个最小堆，但有人可以向我解释一下 (n1, n2) -> n1 - n2 returns 最小元素是如何形成的吗？

Answer 1

这是一个比较器，此 PriorityQueue 实例将使用它来比较项目。它应该是 Comparator 接口的实现，但在这里它简化为所谓的 lambda 表达式 (n1, n2) -> n1 - n2.

顺便说一句，在你的情况下，最好使用预定义的比较器，如 Comparator.reverseOrder()。

Answer 2

构造函数接受一个Comparator<? super E> comparator。

基本上语句 (n1, n2) -> n1 - n2 只是

的 shorthand

Comparator<Integer> result = new Comparator<Integer>() {
        @Override
        public int compare(Integer n1, Integer n2){
            return n1.compareTo(n2);
        }
    };

PriorityQueue<Integer> heap = new PriorityQueue<Integer>(result);

Answer 3

来自 the documentation for this PriorityQueue constructor:

Creates a PriorityQueue with the default initial capacity and whose elements are ordered according to the specified comparator.

所以您正在传递一个提供 Comparator 的 lambda。看着 its documentation:

Compares its two arguments for order. Returns a negative integer, zero, or a positive integer as the first argument is less than, equal to, or greater than the second.

所以在我们的例子中，如果n1小于n2，我们将return一个负数，意思是n1小于n2 并将 n1 移近堆的顶部。

如果我们想反转排序顺序，我们可以将 lambda 更改为：

(n1, n2) -> n2 - n1

Answer 4

问题已经回答。我只是想添加一个更简单的演示。

使用 Comparator#compare 时，两个整数按照比较函数的结果进行比较。

 * Result is negative -> first element is smaller
 * Result is 0        -> they are same
 * Result is positive -> first element is greater

当您使用n1 - n2时：

* Result is negative -> n1 is smaller
* Result is 0        -> n1 and n2 are same
* Result is positive -> n1 is greater

当您使用n2 - n1时：

* Result is negative -> n2 is smaller
* Result is 0        -> n1 and n2 are same
* Result is positive -> n2 is greater

编辑

下面table只是为了演示减法可以用于比较操作。如果操作数和结果不符合数据类型，任何操作都会产生错误的结果。

Java 中的优先级队列（最小堆）排序

Priority queue (Min Heap) ordering in Java

java

heap