当其元素改变优先级时更新 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).

如果你想写一个包装器，你可以将比较代码从入队移到出队.您将不再需要在排队时排序(因为如果您允许更改，它创建的顺序无论如何都不可靠).

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屋！