当其元素更改优先级时更新Java PriorityQueue
我正在尝试使用PriorityQueue来使用Comparator来sorting对象。
这可以很容易地实现，但对象类variables（比较器计算优先级时）可能会在初始插入后发生变化。 大多数人都提出了简单的解决scheme：删除对象，更新值并重新插入，因为这是优先级队列的比较器投入使用时的情况。
除了在PriorityQueue上创build一个包装类外，还有更好的方法吗？
您必须删除并重新插入，因为插入时将新元素置于适当的位置，因为队列工作正常。 这比每次退出队列时都要find最高优先级的元素要快得多。 缺点是在元素插入后你不能改变优先级。 一个TreeMap具有相同的限制（就像一个HashMap，当插入后其元素的哈希码发生变化时也会中断）。
如果你想编写一个包装器，你可以把比较代码从入队转移到出队。 你不需要在排队时间进行sorting（因为如果你允许改变，它创build的顺序不会是可靠的）。
但是这将会变得更糟，如果你改变了任何优先级，你想在队列上进行同步。 由于需要在更新优先级时添加同步代码，因此您可能只需要出队和入队（两种情况下都需要引用队列）。
我不知道是否有Java实现，但是如果您要更改键值，则可以使用Fibonnaci堆，它具有O（1）摊销成本以减less堆中条目的键值，而比在普通堆中的O（log（n））要多。
这取决于你是否直接控制了值的变化。
如果你知道值的改变，你可以删除并重新插入（这实际上是相当昂贵的，因为删除需要对堆进行线性扫描！）。 此外，对于这种情况，您可以使用UpdatableHeap结构（不包括java股票）。 从本质上讲，这是一个跟踪哈希表中元素位置的堆。 这样，当一个元素的优先级改变时，它可以修复堆。 第三，你可以找一个相同的斐波纳契堆。
根据您的更新速度，每次都可以使用线性扫描/快速sorting/ QuickSelect。 特别是如果你有更多的更新比pull s，这是要走的路。 QuickSelect可能是最好的，如果你有批次的更新，然后批量的拉操作。
