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

gab6jxml  于 2021-07-06  发布在  Java
关注(0)|答案(1)|浏览(378)

这个问题在这里已经有答案了

priorityqueue.tostring元素顺序错误(4个答案)
上个月关门了。
我正在对最小优先级队列和最大优先级队列进行编码,如下所示:

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]是样本输入,并且打印优先级队列的输出是:
最小值:[3.0,4.0,5.0,12.0,8.0,7.0]最大值:[12.0,8.0,7.0,3.0,4.0,5.0]
我定义的比较器有什么问题吗?事先谢谢你的帮助。

aiazj4mn

aiazj4mn1#

当您迭代 PriorityQueue 这些元素不是完全有序的。你唯一能确定的是 PriorityQueue 将强制最小和最大的元素是 min_pq 以及 max_pq 优先级队列。
从priorityqueue javadocs:
此队列的头是相对于指定顺序最少的元素。
基于此假设,如果使用此方法,则可以按顺序打印 poll() :

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

投票方式:
检索并删除此队列的头,如果此队列为空,则返回null。
用于比较 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));

或者,代替 PriorityQueue ,你可以选择 TreeSet ,然后可以根据所选的比较器按顺序遍历元素,而不必删除任何元素。

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

相关问题