最小优先级队列和最大优先级队列排序不正确[重复]

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将强制执行最小和最大元素分别是minu-pq和max-pq优先级队列的第一个元素。

来自PriorityQueue javadocs：

这个队列的头是相对于指定排序的最小元素。

基于此假设，如果使用方法poll（），则可以按顺序打印：

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

投票方式：

检索并删除此队列的头，如果此队列为空，则返回null。

要比较Doubles，应使用Double方法。比较（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的另一个好处是，它附带了方法khendingSet（）。因此，您不需要保留两个数据结构来保持min和max的顺序，相反，您可以只使用：

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