java - Java のプライオリティ キュー

Question

java.util.PriorityQueueComparator構築時にa を渡すことができます。要素を挿入するとき、それらはコンパレータによって指定された優先度に従って並べ替えられます。

挿入後に要素の優先度が変わるとどうなりますか? PriorityQueue要素が並べ替えられるのはいつですか? 実際には最小の優先度を持たない要素をポーリングすることは可能ですか?

効率的な優先度の更新を可能にする優先度キューの適切な実装はありますか?

Answer 1

要素は挿入時に順序付けが行われるため、要素を削除して変更し、再挿入する必要があります。いくつかの手順が必要ですが、効率的で十分かもしれません。（削除についてのコメントがO（n）であることに気づきました。）

1つの問題は、要素を削除したときにも並べ替えられることです。これは、しばらくしてから再挿入する場合は冗長です。独自の優先度キューを最初から実装する場合、このステップをスキップするupdate（）を使用できますが、ベースによって提供されるremove（）とadd（）に制限されているため、Javaのクラスの拡張は機能しません。

Answer 2

私は物事を並べ替えないことを期待しPriorityQueueます-そしてそれが新しいエントリを置くための正しい場所を見つけるために二分探索を行おうとすると非常に混乱するかもしれません。

一般的に言って、ハッシュテーブルのキーを構成する値を変更するのと同じように、すでにキューにあるものの優先度を変更することは悪い考えだと思います。