当前位置: 首页 > 知识库问答 >
问题:

Java:PriorityQueue从自定义比较器返回不正确的顺序?[副本]

黄查猛
2023-03-14

我已经编写了一个自定义比较器来比较我的节点类,但是java优先级队列没有以正确的顺序返回我的项。

这是我的比较器:

public int compare(Node n1, Node n2){

    if (n1.getF() > n2.getF()){
        return +1;
    }
    else if (n1.getF() < n2.getF()){
        return -1;
    }
    else {  // equal
        return 0;
    }
}

其中getF返回一个双精度。然而,在将几个节点插入优先级队列后,我使用以下方法将它们打印出来:

while(open.size() > 0) {
    Node t = (Node)(open.remove());
    System.out.println(t.getF());
}

其结果是:

6.830951894845301
6.830951894845301
6.0
6.0
5.242640687119285
7.4031242374328485
7.4031242374328485
8.071067811865476

你知道为什么会这样吗?我的比较器错了吗?谢谢

麦克

共有2个答案

龙凯
2023-03-14

不知道你的代码有什么问题,但这对我有用:

import java.util.*;
public class Test {
    public static void main(String[] args) {
        PriorityQueue<Node> open = new PriorityQueue<Node>(10,
                new Comparator<Node>() {
            @Override
            public int compare(Node n1, Node n2){
                if (n1.getF() > n2.getF()){
                    return +1;
                }
                else if (n1.getF() < n2.getF()){
                    return -1;
                }
                else {  // equal
                    return 0;
                }
            }
        });

        for (int i = 0; i < 20; i++)
            open.add(new Node());

        while(open.size() > 0) {
            Node t = (Node)(open.remove());
            System.out.println(t.getF());
        }
    }
}

class Node {
    double d = Math.random() * 10;
    public double getF() { return d; }
}

输出:

0.21442281608773262
1.9965384843480016
2.6660026888929824
2.888889937975976
3.098932914222398
3.1059072964534638
4.193212975907516
4.296282412431935
4.3241392173963735
4.825876226139123
5.193550353435191
5.637831708672641
5.949759449054407
6.620639629878806
7.505126870725806
7.966337123623846
8.270840212631589
8.484502118941545
8.730910327480023
9.191324325662219

确保getF()不会意外地返回一个int-version的双版本。

更新:您不能更新定义插入后元素顺序的数据。在这种情况下,您需要提取元素,更新它,并重新插入它。

谭建章
2023-03-14

你如何打印出这些值?我不认为PriorityQueue中的迭代器提供了与整个类相同的排序保证,所以如果您正在做

for(Node n : queue) {
System.out.println(n.getF());
}

你会得到无序的输出。排序保证只适用于offerake轮询peek,可能还有其他一些方法。

javadocs for priority队列中特别提到了迭代器http://java.sun.com/javase/6/docs/api/java/util/PriorityQueue.html

 类似资料:
  • 问题内容: 我想为汽车清单开发一个排序演示。我正在使用数据表显示汽车列表。现在实际上我想按汽车颜色对列表进行排序。这里不是按字母顺序排序的。我想使用我的自定义排序顺序,例如先是红色汽车,然后是蓝色,等等。 为此,我尝试使用,但它只允许按字母顺序排序。 因此,任何人都可以指导我实现使用该技术的方法,以便使排序变得更快。 问题答案: 我建议你为汽车颜色创建一个枚举,而不要使用字符串,并且枚举的自然顺序

  • 在我的PriorityQueue中,我有两种类型的客户,即VIP和常规客户。我想先为贵宾服务,再为常客服务。 如果CustomerID<100,则视为VIP。 如果客户是VIP,他会排在队列中VIP部分的最后 更新:我不想排序任何其他列除了VIP。我不想添加“日期”,因为它感觉像是一个黑客,而不是理解Java是如何工作的。

  • 我想通过提供自定义顺序对包含不相关对象的列表进行排序。例如,我要排序的列表包含Animal类的对象。动物对象有一个名为type的对象,可以是猫、老鼠或狗。我有一个自定义订单鼠标 一种解决方案是手动检查类型的类(通过 instanceof)并在比较器中对顺序进行硬编码。但是,我有太多可以包含在 Animal 中的类(在本例中不仅包含三个类),因此这将产生大量的 if 案例。

  • 我读到这些方法返回值的规则是,对于obj1.compareTo(ob2),例如,如果ob2在层次结构中位于ob1之下,则返回值为负值,如果它位于ob1之上,则返回值为正(如果它等于,则返回值为0)。然而,在我的类中,我看到了使用Math.signum在compareTo方法中获得-1(表示负值)和1(表示正值)的示例。 有什么原因吗? 编辑: 以下是我的意思:

  • 我也可以使用相同的比较器按Id对列表进行排序吗?

  • 问题内容: 比较器内部的返回值实际上是什么意思? 例如 : 如果返回类型为1,则其实际返回 [20、10、30、100] 如果返回类型为-1,则其实际返回 [100,30,10,20] 如果返回类型为0,则其实际返回 [20] 请告诉我这表示什么? 问题答案: 返回值(不是类型是)告诉调用者(对数据进行排序的事物): 如果始终为比较器返回相同的值(o,1,-1),而不管其输入如何,那么您使用的是错