java - Java中的优先级队列

Question

java.util.PriorityQueue允许Comparator在构建时通过。插入元素时，根据比较器指定的优先级对其进行排序。

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

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

Answer 1

您应该删除元素，更改它，然后重新插入，因为在插入时会发生排序。尽管它涉及几个步骤，但它的效率可能已经足够了。（我刚刚注意到关于删除是 O(n) 的评论。）

一个问题是，当您删除元素时它也会重新排序，如果您稍后要重新插入它，这是多余的。如果您从头开始实现自己的优先级队列，您可能有一个跳过此步骤的 update()，但扩展 Java 的类将不起作用，因为您仍然受限于基础提供的 remove() 和 add()。

Answer 2

我希望PriorityQueue不会重新排序 - 如果它尝试进行二进制搜索以找到放置任何新条目的正确位置，它可能会变得非常困惑。

一般来说，我希望更改队列中已经存在的某些内容的优先级是一个坏主意，就像更改组成哈希表中键的值一样。