Collections.reverseOrder 与自定义比较器之间的区别

Question

我希望这两个代码片段会产生相同的结果，但它们不会。为什么？唯一的区别是传递给 PriorityQueue 构造函数的 Comparator。

import java.util.Collections;
import java.util.PriorityQueue;

public class PriorityQueueTest {

  public static void main(String[] args) {
    PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
    int[] arr = {2,3,9,8,4};
    for (int i=0; i<arr.length; i++) {
      pq.add(arr[i]);
    }
    while(pq.size()>0) {
      System.out.println(pq.poll());
    }
  }
}

输出（正确/预期）：

import java.util.Collections;
import java.util.PriorityQueue;

public class PriorityQueueTest {

  public static void main(String[] args) {
    PriorityQueue<Integer> pq = new PriorityQueue<>((a,b) -> a>b ? 0 : 1);
    int[] arr = {2,3,9,8,4};
    for (int i=0; i<arr.length; i++) {
      pq.add(arr[i]);
    }
    while(pq.size()>0) {
      System.out.println(pq.poll());
    }
  }
}

输出（错误/意外）：

Answer 1

我缺少的是在比较器中返回 0 表示值相等。

将比较器更改为以下命令正确

(a,b) -> a>=b ? -1 : 1

Answer 2

比较器必须 return 3 种状态：负数、0 或正数，并且必须是自洽的，这样当 a!=b 和零时 compare(a,b) 与 -compare(b,a) 具有相同的符号如果 a.equals(b).

您的比较器不满足这些条件。您很幸运，您的答案有效，但如果您在其他比较器中省略 0 案例，您将来可能会遇到问题。

改为使用：

PriorityQueue<Integer> pq = new PriorityQueue<>((a,b) -> a==b ? 0 : a>b ? -1 : 1);

上面的return是你期望的元素顺序Collections.reverseOrder()。

Collections.reverseOrder 与自定义比较器之间的区别

Difference between Collections.reverseOrder vs custom comparator

java

data-structures

priority-queue