Java：PriorityQueue从自定义比较器返回不正确的排序？

我写了一个自定义比较器来比较我的节点类，但是java优先级队列没有以正确的顺序返回我的项目。Java：PriorityQueue从自定义比较器返回不正确的排序？

这里是我的比较：

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返回一个double。将几个节点到优先级队列后，但是，我打印出来使用：

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

任何想法，为什么会这样？我的比较器是否错误？谢谢。

Mike

来源

2010-06-15 Michael Simpson

实际的Java类是你的“java优先队列”（我认为是PriorityQueue），你是如何构造它的？ – Gray 2010-06-15 19:59:14

java.util.PriorityQueue，我假设？ – Ceilingfish 2010-06-15 20:00:10

不回答你的问题，但我注意到你可以简化你的比较器： 'return Double.compare（n1.getF（），n2.getF（））;' – 2010-06-15 20:00:37

如何打印出这些值？我不认为从PriorityQueue迭代器提供了整体类不相同的排序保证，所以潜在的，如果你正在做

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

你会得到无序的输出。订购保证仅适用于offer,take,poll,peek，以及可能的其他一些方法。

有在的Javadoc优先级队列的迭代器特别提及http://java.sun.com/javase/6/docs/api/java/util/PriorityQueue.html

来源

2010-06-15 19:59:36 Ceilingfish

这是正确的;来自'iterator（）'方法的'PriorityQueue' javadoc：“迭代器不以任何特定顺序返回元素。” – 2010-06-15 20:02:50

“你是如何印出这些价值的？”......这个问题说“我用...印出来”。 – aioobe 2010-06-15 20:12:17

我没有使用迭代器。比较器 comparator = new NodeComparator（）; PriorityQueue open = new PriorityQueue （INITIAL_SIZE，comparator）; 然后上面的while循环。 – 2010-06-15 20:38:11

不知道什么是你的代码错误，但是这对我的作品：

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()不会意外返回double的整型版本。

更新：您无法更新定义插入后元素顺序的数据。在这种情况下，您需要提取元素并进行更新，然后重新插入元素。

来源

2010-06-15 20:02:17 aioobe

你可以尝试使用类迭代器吗？看看你是否得到无序的输出？ – Ceilingfish 2010-06-15 20:04:03

然后它没有正确排序。说得通。如果它是作为堆实现的，它只知道下一个要移除的元素是哪个。 – aioobe 2010-06-15 20:07:14

嗯......我先将节点添加到prio队列中，然后使用Node的“setF”函数更改f值。插入对象后，有没有在prio队列中更新值的问题？即使我指向prio队列中的节点？ @Ceilingfish - 我的节点类将f值初始化为-1，然后插入prio队列，然后更新f val。这与你上面的例子不同。我很感谢你检查基本逻辑，但谢谢。 – 2010-06-15 20:37:25

Java：PriorityQueue从自定义比较器返回不正确的排序？

回答

相关问题