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

发布于 2024-09-06 06:17:29 字数 699 浏览 1 评论 0原文

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

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

麦克风

原文

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.

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:

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

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

紧拥背影 2024-09-13 06:17:29

你如何打印这些值？我不认为 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

How are you printing out those values? I don't think the iterator from PriorityQueue provides the same ordering assurances that the overall class does, so potentially if you're doing

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.

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

回复收藏 0 原文

别理我 2024-09-13 06:17:29

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

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 的 int 版本。

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

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.

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.

回复收藏 0 原文

~没有更多了~