PriorityQueue.toString() が PriorityQueue 内の項目の順序を正確に反映しないのはなぜですか?

PriorityQueue.toString() 順序付けの異常: 説明

PriorityQueue から要素を取得しようとすると、出力が次の場所で予期しない動作に遭遇する可能性があります。順序が予想される優先度と一致しません。これは、PriorityQueue.toString() がキューの内部状態のスナップショットのみを提供し、並べ替えられた順序を表していない可能性があるためです。

この問題に対処するには、toString() に依存する代わりに、ポーリングする必要があります。 poll() メソッドを使用してキューから項目を 1 つずつ取得します。その理由は次のとおりです。

ヒープ構造とキューの順序付け

内部では、PriorityQueue はヒープ データ構造を利用して、並べ替えられた順序を効率的に維持します。ただし、ヒープは常に完全にソートされているわけではありません。代わりに、これは部分的に順序付けされたツリーであり、各ノードがその親および子と比較されます。

キューに項目を追加または削除すると、この部分的な順序を維持するためにヒープが調整されます。その結果、キューで toString() を呼び出すと、現在の状態のスナップショットのみが表示され、予想される優先順位と一致しない可能性があります。

解決策: Poll() を使用する

ソートされた順序で要素を取得するには、poll() メソッドを使用して要素を 1 つずつポーリングする必要があります。 poll() メソッドはヒープの最上部で動作し、残りのノードの順序を維持しながらルート ノードを削除します。

コード例

これを説明するには、次のようにします。コードへの次の変更を検討してください:

<code class="java">import java.util.Comparator;
import java.util.PriorityQueue;

public class TreeNodeHuffman {

    public static void main(String[] args) {
        HuffmanComparator compare = new HuffmanComparator();

        // Create and initialize PriorityQueue
        PriorityQueue<TreeNodeHuffman> queue = new PriorityQueue<>(26, compare);
        // ... Add nodes to the queue

        // Poll and print items
        while (!queue.isEmpty()) {
            System.out.println(queue.poll());
        }
    }
}</code>

poll() メソッドを利用すると、要素がキューから削除されるときに要素を並べ替えられた順序で表示できるようになります:

[z, q, x, j, k, v, b, m, i, c, e, s, o, w, a, r, h, p, t, l, a]

これは、頻度が最も低い要素を最初に取得するという期待と一致します。

以上がPriorityQueue.toString() が PriorityQueue 内の項目の順序を正確に反映しないのはなぜですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。