Java:优先级队列实现可按正确顺序迭代

Question

我正在寻找 Java 中 PQ 的一些实现，它允许按 PQ 顺序迭代 - 首先是顶级元素，然后是下一个元素等等。我尝试使用 TreeSet(它实现了 NavigableSet)，但它导致了一个问题。就我而言:

• 我正在为我的对象使用 Comparator
• 由于某些外部操作导致优先级发生变化
• 如果优先级发生变化，我知道哪个对象的优先级发生变化，但我不知道它是以前的优先级

作为最后一点的结果 - 当我想更新其优先级时，我无法在 TreeSet 中找到我的元素:/ 你碰巧知道:遵守这个的聪明方法吗？或者以“好”的方式迭代的PQ的一些实现？还是我应该创建一些链接的数据结构来匹配对象及其在树中的位置？

更新:

• 并发不是问题
• 对象无法从 TreeSet 中删除，因为它的优先级已更改，因此 Comparator 的计算方式将不同，并且不会在此数据结构中找到对象。插入不是问题。
• 我不能使用 compareTo 方法，因为此优先级不是比较这些对象的正确方法。这就是为什么我需要使用 Comparator

可能的解决方案:

• 创建类PrioritizedObject，它将按优先级进行比较并保留我的对象
• 使用 map :我的对象 -> PrioritizedObject
• 将 PrioritizedObject 保留在一些 NavigableSet 中

我会使用这张 map 从 NavigableSet 中移除对象。如果我添加一些东西，当然会用新元素更新它。 问题是我将不得不从这个 NavigableSet 包装迭代器以使迭代器返回我的对象​​。

有没有更好的解决方案？

Answer 1

if priority changes I know for which object, but I don't know it's previous priority

你不需要知道它之前的优先级。您所要做的就是将其移除并重新插入。