Java中的优先级队列

Question

java.util.PriorityQueue允许Comparator在施工时通过.插入元素时,会根据比较器指定的优先级对它们进行排序.

插入元素后,当元素的优先级发生变化时会发生什么？什么时候PriorityQueue重新排序元素？是否可以轮询实际上没有最低优先级的元素？

是否有优先级队列的良好实现,允许有效的优先级更新？

Answer 1

您应该删除元素,更改它并重新插入,因为在插入时会发生排序.虽然它涉及几个步骤,但它的效率可能足够好.(我刚注意到关于删除的评论是O(n).)

一个问题是,当你删除元素时它也会重新排序,如果你稍后再重新插入它,这是多余的.如果从头开始实现自己的优先级队列,则可以使用update()跳过此步骤,但扩展Java的类将无法工作,因为您仍然只能使用base提供的remove()和add().

Answer 2

我希望在PriorityQueue不重新排序的东西-如果它试图做一个二进制搜索找到把任何新的条目正确的地方就可以得到非常困惑.

一般来说,我希望改变已经在队列中的东西的优先级是一个坏主意,就像更改构成哈希表中的键的值一样.