6

ノード クラスを比較するカスタム コンパレータを作成しましたが、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

これがなぜそうなのか、何か考えはありますか？私のコンパレータは間違っていますか？ありがとう。

マイク

4

2 に答える 2

10

これらの値をどのように出力していますか? からのイテレータは、クラス全体が提供するのと同じ順序保証を提供するとは思わない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

于 2010-06-15T19:59:36.113 に答える
4

コードの何が問題なのかわかりませんが、これは私にとってはうまくいきます:

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 バージョンを誤って返さないようにしてください。

更新: 挿入後に要素の順序を定義するデータを更新することはできません。その場合、要素を抽出して更新し、再挿入する必要があります。

于 2010-06-15T20:02:17.783 に答える