5

簡単に言えば、私はグラフを実装していて、現在はクルスカルに取り組んでいます。優先キューが必要です。優先度キューの私の定義は、最小のキーを持つ要素が最初に来るということですか? これは間違っていますか？重み付けされたエッジ (または数値) をキューに挿入すると、並べ替えられないためです。

PriorityQueue<Integer> tja = new PriorityQueue<Integer>(); 
tja.add(55);
tja.add(99); 
tja.add(1); 
tja.add(102);
tja.add(54);
tja.add(51);
System.out.println(tja);

これはこれを出力します。[1、54、51、102、99、55]。これは、私が望むようにソートされていません! はい、エッジ オブジェクトから数値を抽出し、その int に基づいて比較するプライオリティ キューに入るコンパレータを作成しました。それで、これはうまくいくはずですか、それとも、このデータ構造がどのように機能するかという概念全体を完全に誤解したのでしょうか?

4

3 に答える 3

17

System.out.println が toString() メソッドを呼び出していますが、これはイテレータを使用していますが、自然順序付けが保証されていません。ドキュメントから：「メソッド iterator() で提供される Iterator は、特定の順序で優先度キューの要素をトラバースすることが保証されていません。」

于 2009-11-25T09:02:19.990 に答える
7

私はJavaでの経験はありませんが、優先事項がまたは（を使用する）PriorityQueueに統合されていないようです。iterator()toString()iterator()

もしあなたがそうするなら：

    while (tja.size()>0)
        System.out.println(tja.remove());

適切な結果が得られます。

于 2009-11-25T09:00:46.090 に答える
1

バイナリ ヒープの機能に精通していますか? そうでない場合は、最小ヒープ構造と最大ヒープ構造を調べてください。PriorityQueue はヒープに実装されています。PriorityQueue はアイテムを昇順でソートしませんが、ヒープソートを行います。

リンクをたどる: Priority Queue

得られる出力は正しいです。

于 2015-03-18T11:30:03.237 に答える