在元素更改优先级时更新Java PriorityQueue [英] Updating Java PriorityQueue when its elements change priority

问题描述

我正在尝试使用 PriorityQueue 使用 Comparator 订购对象。

I'm trying to use a PriorityQueue to order objects using a Comparator.

这可以很容易地实现，但是对象类变量（比较器计算优先级）可能会在初始插入后发生变化。大多数人建议删除对象，更新值并重新插入它的简单解决方案，因为这是优先级队列的比较器投入使用时。

This can be achieved easily, but the objects class variables (with which the comparator calculates priority) may change after the initial insertion. Most people have suggested the simple solution of removing the object, updating the values and reinserting it again, as this is when the priority queue's comparator is put into action.

是否存在除了在PriorityQueue周围创建一个包装类之外，还有一个更好的方法吗？

Is there a better way other than just creating a wrapper class around the PriorityQueue to do this?

推荐答案

你必须删除并重新插入，因为队列在插入时将新元素放在适当的位置。这比每次退出队列时找到最高优先级元素的选择要快得多。缺点是在插入元素后无法更改优先级。 TreeMap具有相同的限制（HashMap也是如此，当插入后其元素的哈希码发生变化时也会中断）。

You have to remove and re-insert, as the queue works by putting new elements in the appropriate position when they are inserted. This is much faster than the alternative of finding the highest-priority element every time you pull out of the queue. The drawback is that you cannot change the priority after the element has been inserted. A TreeMap has the same limitation (as does a HashMap, which also breaks when the hashcode of its elements changes after insertion).

如果你想写一个包装器，你可以将比较代码从enqueue移动到dequeue。您不需要再排队入队时间（因为如果您允许更改，它创建的顺序无论如何都不可靠。）

If you want to write a wrapper, you can move the comparison code from enqueue to dequeue. You would not need to sort at enqueue time anymore (because the order it creates would not be reliable anyway if you allow changes).

但这会更糟糕，而你如果您更改任何优先级，则希望在队列上进行同步。由于您需要在更新优先级时添加同步代码，因此您可能只是出列并入队（在两种情况下都需要对队列的引用）。

But this will perform worse, and you want to synchronize on the queue if you change any of the priorities. Since you need to add synchronization code when updating priorities, you might as well just dequeue and enqueue (you need the reference to the queue in both cases).

这篇关于在元素更改优先级时更新Java PriorityQueue的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！