java - PriorityQueue 是正确的数据结构吗？

Question

我需要存储具有执行时属性和对执行者(单元)本身的引用的操作对象。当一个单元执行某个操作时，它会连同执行该操作所需的时间一起添加到 PriorityQueue 中。该表演者不得再次表演，直到再次成为列表中的第一位。我以前从未使用过优先级队列，所以我不知道它的功能。

那么如何解决这个问题呢？让我们看一下以下排序的操作:

time:1600 -> unit:1
time:3700 -> unit:2
time:12000 -> unit:3

现在我想访问此数据结构，并将所有这些 time 属性降低 1600，并使第一单元能够再次执行。如果我继续增加时间，我很快就会达到最大值。我可以使用很长一段时间，但最终我会遇到同样的问题。无论如何，我想对于每种类型，我都必须遍历完整列表或设置以更改其中的对象属性。插入时，我只是比较像 PriorityQueue 这样的结构中快速插入的时间。

那么我应该使用什么数据结构呢？

Answer 1

您可以轻松地从优先级队列中删除第一个元素。

我建议您应该使用一个额外的整数值delta，其中您 可以存储差异。 使用此方法，如果从优先级队列中删除节点 3700/单元 2，则只需计算 3700-delta。 删除一个元素后，您必须再次更改此增量。

事实上，您不会通过向所有条目添加特定值来更改优先级队列中的顺序，因此您不必更改数据结构本身。

为了防止增量增加到无穷大，您必须更新所有 增量达到阈值后的条目。 这种方法的优点是，您只需更新数据 元素很少出现。

优先级队列是解决这个问题的最佳方法之一。 主要优点是优先级最低的元素始终是 在顶部。