4

重複の可能性:
Java の PriorityQueue でこの奇妙な順序が発生するのはなぜですか?

以下のコードを参照してください。

public static void main(String[] args) {
    Queue<String> q = new PriorityQueue<String>();
    q.offer("car");
    q.offer("airplane");
    q.offer("bicycle");
    Iterator<String> i = q.iterator();
    while(i.hasNext())
        System.out.print(i.next() + " ");
}

なぜ出力が

airplane car bicycle

それ以外の

airplane bicycle car

?

APIでは、プライオリティ キューの要素は自然な順序に従って並べられると記述されているためです。

4

2 に答える 2

9

iterator のjavadocによると：

イテレータは特定の順序で要素を返すわけではありません。

ただし、最初の項目 (head) は最小であることが保証されています。したがって、これはあなたが期待するものを出力するはずです:

public static void main(String[] args) throws Exception {
    Queue<String> q = new PriorityQueue<String>();
    q.offer("car");
    q.offer("airplane");
    q.offer("bicycle");
    String e = null;
    while ((e = q.poll()) != null) {
        System.out.println(e);
    }
}

繰り返しをソートしたい場合は、別の構造を使用する必要があります。たとえば、TreeSet重複がない場合です。

于 2012-12-02T11:13:42.930 に答える
2

PriorityQueue は優先ヒープに基づいています。このデータ構造により、要素がソートされていなくても、最小の要素を非常に迅速に取得できます。PriorityQueue への要素の追加は、ツリー ベースの TreeSet よりも高速です。要素はソートされていないため、イテレータは、API が言うように、「特定の順序で要素を返すことはありません」。

于 2012-12-02T12:48:23.553 に答える