Java：PriorityQueue从自定义比较器返回错误的排序？

我编写了一个自定义比较器来比较我的节点类，但是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返回一个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 

任何想法为什么会这样？ 我的比较器错了吗？ 谢谢。

麦克风

Answer 1

你是如何打印出这些价值的？ 我不认为PriorityQueue的迭代器提供与整个类相同的排序保证，所以如果你做的话可能

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

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

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

Answer 2

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

 import java.util.*; public class Test { public static void main(String[] args) { PriorityQueue open = new PriorityQueue(10, new Comparator() { @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的int版本。

---

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