優先順位リストを表す効率的なデータ構造を探しています。具体的には、一連のアイテムに優先度を割り当て、最高得点のアイテムのみを返す必要があります。ヒープ上で動作するプライオリティ キューを調べましたが、実際には私のニーズに合わないようです。キューから最高評価のアイテムをポーリングするとすぐに、ヒープ構造が再編成されます。
もちろん、最も簡単な解決策はリンクされたリストですが、最悪の場合、挿入操作にかなりの時間がかかります。
誰かがより良い解決策を持っていますか?
6562 次
5 に答える
5
ヒープは非常に適しているようで、間違った方向に進んでいるようです。
上位のx要素が必要だとします（このxはnと比較してどうですか？）
あなたがしていることは、すべてを最大ヒープに入れて、トップxを取得することです。
代わりに、正確にx個の要素の最小ヒープを使用することをお勧めします。
ヒープに挿入する最初のx要素。
次の着信要素では、ヒープ内で非常に高速（O（1）時間）に実行できる最小値と比較します。小さい場合は、入力要素を無視します。
着信要素がminより大きい場合は、minを着信要素に増やし、ヒープ内でふるいにかけます。これは最悪の場合logx時間になるはずです。
（nlogx時間で）完了すると、O（xlogx）時間でソートされた順序でヒープから要素を取得できます。
データの大きさ（およびxの小ささ）によっては、この最小ヒープソリューションの使用が非常に高速になる可能性があります。
挿入を本当に超高速にし、検索をあまり気にしない場合は、次のこともできます。
要素をベクトル（償却されたO（1）挿入時間の配列）にそれらが来る順序で挿入します。
選択アルゴリズムを使用して、x番目に大きい要素を見つけます（O（n）時間ですが、定数が大きい場合があります）。その番号がSだとしましょう。
次に、各要素をSと比較して配列をウォークし、Sと同じ大きさの要素を選択します。
xが適度なサイズで、nに匹敵する場合（n / 2など）、これは問題なく機能する可能性がありますが、xがnに比べて小さい場合は、最小ヒープを使用することをお勧めします。
于 2010-07-14T15:14:11.910 に答える
4
k個の上位アイテムのみが必要で、他のアイテムを探す必要がない場合は、現在の上位k個のアイテムと数値（リスト内の要素の最低スコア）のみを格納する単純なリンクリストまたは配列を使用できます。
このAdd()操作では、リスト内の最悪の値を持つアイテムを単純に比較し、より適切な場合は、現在の最悪のアイテムを追加されたアイテムと交換します。現在最悪のスコアを持つ要素を見つける必要があるため、挿入の最悪の場合、これにはO（k）時間がかかります。ただし、平均的なケースはO（1）です。これは、リストに適切な要素を追加すると、スワップを実行する必要がある確率が0になる傾向があるためです（つまり、実際にはアイテムを追加していません）。
したがって、要素をランダムに生成すると、パフォーマンスが非常に高くなる可能性があります。注文したアイテムを生成したとしても（最悪の場合）、kの値に対して十分に高速である可能性があります。
于 2010-07-14T12:25:36.837 に答える
4
うーん。リストをスキップしますか? O(log n) の挿入 (ヒープベースのキューとして) が必要ですが、最上位の要素の取得は O(1) [削除を含む] である必要があります。それらは、ロックフリー アルゴリズムを使用して実装することもできます。
于 2010-07-14T11:51:18.640 に答える
1
JDK には、ヒープ アルゴリズムに基づく組み込みの pqueue クラス (java.util.PriorityQueue) があります。
申し訳ありませんが、あなたのニーズに合わないヒープについて少しだけ見ました。理由を説明できますか？カスタム コンパレータを作成する (または項目を比較可能にする) ことができ、PriorityQueue は項目を適切に並べ替えます。
于 2010-07-14T11:54:28.087 に答える