java - 更新元素后重新堆化 java.util.PriorityQueue

Question

我有一个包含对某些对象的引用的 PriorityQueue。当我最初将元素插入优先级队列时，顺序由数据结构维护。现在，在删除操作之后，我更新了一些由优先级队列持有的引用。理想情况下，这需要对优先级队列进行重新堆化操作，但很明显，因为我在外部修改选定的引用，所以无法触发重新堆化。那么，在对队列中的任意元素进行修改的情况下，确保我能够获得像 fast extract max 这样的堆优势的最佳方法是什么？我发现我需要更好的数据结构？

更具体地说，我需要在 Java 中实现类似斐波那契堆的东西。 http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm可以吗？

Answer 1

您可以使用自己的树来代替堆来允许重复元素。不过更简单，您可以使用 TreeMap<PriorityKey, LinkedHashSet<Value>> .所有操作都是 O(log priorityType):

• 添加的是get(priority).add(value) ，如果 get 返回 null，put(priority, new LinkedHashSet())
• 删除任意元素类似，只是如果 Set 为空，则需要从映射中删除优先级。
• 民意调查()是

--

Entry<PriorityKey, LinkedHashSet<Value>> e = map.firstEntry(); 
if (e==null) return null; 
Iterator<Value> i = e.getValue().iterator(); 
Value v = i.next(); //must always have at least one element.
i.remove(); 
if (!i.hasNext()) map.remove(e.getKey());
return v;

如果您需要更改优先级，则必须删除并添加该元素。