最小优先级队列和最大优先级队列排序不正确

Question

我正在编写一个最小优先级队列和一个最大优先级队列，如下所示：

PriorityQueue<Double> max_pq = new PriorityQueue<>(new Comparator<Double>() {
            @Override
            public int compare(Double o1, Double o2) {
                if(o1<o2) return +1;
                if(o1.equals(o2)) return 0;
                return -1;
            }
        });

        PriorityQueue<Double> min_pq = new PriorityQueue<>(new Comparator<Double>() {
            @Override
            public int compare(Double o1, Double o2) {
                if(o1>o2) return +1;
                if(o1.equals(o2)) return 0;
                return -1;
            }
        });

一个输入数组的数字被一个一个地添加到队列中。但是，当数组 [12,4,5,3,8,7] 是样本输入并且打印优先级队列的输出是：

MIN: [3.0, 4.0, 5.0, 12.0, 8.0, 7.0] MAX: [12.0, 8.0, 7.0, 3.0, 4.0, 5.0]

是不是我定义的比较器有问题？预先感谢您的帮助。

Answer 1

当您遍历 PriorityQueue 的元素时，这些元素并不是完全有序的。您唯一可以确定的是 PriorityQueue 将强制 smallest 和 biggest 元素是 [=48= min_pq 和 max_pq 优先级队列的 ]first 个元素。

来自 PriorityQueue javadocs:

The head of this queue is the least element with respect to the specified ordering.

基于该假设，如果您使用 poll():

方法，您可以按顺序打印

while(!max_pq.isEmpty())
{
    System.out.println(max_pq.poll());
}

轮询方法：

Retrieves and removes the head of this queue, or returns null if this queue is empty.

要比较 Double，您应该使用方法 Double.compare(o1, o2)。此外，您可以使用 lambda 和方法引用来简化比较器，即代替 :

PriorityQueue<Double> max_pq = new PriorityQueue<>(new Comparator<Double>() {
            @Override
            public int compare(Double o1, Double o2) {
                if(o1<o2) return +1;
                if(o1.equals(o2)) return 0;
                return -1;
            }
        });

        PriorityQueue<Double> min_pq = new PriorityQueue<>(new Comparator<Double>() {
            @Override
            public int compare(Double o1, Double o2) {
                if(o1>o2) return +1;
                if(o1.equals(o2)) return 0;
                return -1;
            }
        });

你可以使用更优雅和简单的：

PriorityQueue<Double> max_pq = new PriorityQueue<>(Double::compareTo);
PriorityQueue<Double> min_pq = new PriorityQueue<>((o1, o2) -> Double.compare(o2, o1));

或者，您可以选择 TreeSet 而不是 PriorityQueue，这样您就可以根据您选择的比较器按顺序遍历元素，而不必删除任何元素。

TreeSet<Double> max_pq = new TreeSet<>(Double::compareTo);

TreeSet 的另一个好处是它带有方法 descendingSet()。因此，你不需要保留两个数据结构来保持 min 和 max 顺序，相反你可以只：

  TreeSet<Double> max_pq = new TreeSet<>(Double::compareTo);
   
  max_pq.forEach(System.out::println);
  max_pq.descendingSet().forEach(System.out::println);

最小优先级队列和最大优先级队列排序不正确

Min Priority Queue and Max Priority Queue not sorting correctly

java

priority-queue