PriorityQueue の toString メソッドが要素順序の解釈を誤解する仕組み

Java では、PriorityQueue データ構造はバイナリ ヒープを維持し、割り当てられた要素に基づいて要素に優先順位を付けます。比較戦略。この戦略は通常、提供されたコード スニペットに見られるように、カスタム コンパレーターを通じて実装されます。ただし、PriorityQueue の toString メソッドの出力を調べるとき、要素の順序に関してよくある誤解があります。

toString メソッドは、PriorityQueue の内容のテキスト表現を提供するように設計されています。ただし、コンパレータによって定義された優先順位が暗黙的に適用されるわけではありません。代わりに、要素がヒープ内の現在の位置に表示されるだけで、予想される並べ替え順序と一致しない可能性があります。

指定された例では、頻度値に優先順位を付けるために、PriorityQueue がカスタム Comparator で初期化されます。出力ではこの順序を反映し、周波数の低い要素が最初にリストされるようにすることを意図しました。ただし、toString メソッドの出力には間違った順序が表示され、意図した優先度と明らかに矛盾しています。

この矛盾の原因はバイナリ ヒープの内部構造にあります。部分的な順序付けは維持されますが、要素はヒープから削除されるまで完全には並べ替えられません。 toString メソッドは、この並べ替えを実行せずにヒープから要素を直接取得し、観察された出力が得られます。

この問題に対処し、正しい並べ替え順序を取得するには、PriorityQueue から要素を 1 つずつ抽出する必要があります。 1つ。 poll() メソッドはこれを実行し、ヒープから要素を削除してそれを返します。 poll() を使用して PriorityQueue を反復処理し、返された要素を出力することで、意図したとおりに並べ替えられた順序を取得できます。

したがって、要素を並べ替えられた順序で出力するための正しいコードは次のようになります。

while (!queue.isEmpty()) {
   System.out.println(queue.poll());
}

これにより、コンパレータで定義されたように、要素が頻度の昇順で出力されます。