Java：PriorityQueue 从自定义比较器返回错误的排序？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/3048515/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Java: PriorityQueue returning incorrect ordering from custom comparator?
提问by Michael Simpson
I've written a custom comparator to compare my node classes, but the java priority queue is not returning my items in the correct order.
我已经编写了一个自定义比较器来比较我的节点类，但是 java 优先级队列没有以正确的顺序返回我的项目。
Here is my comparator:
这是我的比较器：
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;
}
}
Where getF returns a double. However after inserting several Nodes into the priority queue, I print them out using:
getF 返回双精度值的地方。但是，在将多个节点插入优先级队列后，我使用以下命令将它们打印出来：
while(open.size() > 0) {
Node t = (Node)(open.remove());
System.out.println(t.getF());
}
Which results in:
结果是：
6.830951894845301
6.830951894845301
6.0
6.0
5.242640687119285
7.4031242374328485
7.4031242374328485
8.071067811865476
Any ideas why this is so? Is my comparator wrong? Thanks.
任何想法为什么会这样？我的比较器错了吗？谢谢。
Mike
麦克风
回答by Ceilingfish
How are you printing out those values? I don't think the iterator from PriorityQueueprovides the same ordering assurances that the overall class does, so potentially if you're doing
你如何打印出这些值？我不认为迭代器 fromPriorityQueue提供与整个类相同的排序保证，所以如果你正在做
for(Node n : queue) {
System.out.println(n.getF());
}
You'll be getting unordered output. The ordering assurance only applies to offer, take, poll, peek, and possibly some other methods.
你会得到无序的输出。排序保证仅适用于offer，take，poll，peek，可能还有一些其他的方法。
There's a special mention on the iterator in the javadocs for priority queue http://java.sun.com/javase/6/docs/api/java/util/PriorityQueue.html
优先级队列的 javadocs 中的迭代器有一个特别提及http://java.sun.com/javase/6/docs/api/java/util/PriorityQueue.html
回答by aioobe
Don't know what's wrong with your code, but this works for me:
不知道你的代码有什么问题，但这对我有用：
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; }
}
Output:
输出：
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
Make sure getF()doesn't accidentally return an int-version of the double.
确保getF()不会意外返回 double 的 int 版本。
Update: You cannot update the data which defines the order of the elements after insertion. In that case you need to extract the element, updated it, and reinsert it.
更新：您不能更新定义插入后元素顺序的数据。在这种情况下，您需要提取元素，更新它，然后重新插入它。
