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

Question

我有一个包含对象引用的优先队列。当我最初将元素插入优先队列时，数据结构会维护它们的顺序。现在，在删除操作之后，我更新了一些由优先队列持有的引用。理想情况下，这需要对优先队列进行重新堆化操作，但显然，由于我正在外部修改选定的引用，因此无法触发重新堆化操作。那么，在任意元素内部队列发生修改的情况下，如何确保我能够获得类似堆的快速提取最大值的优势？我认为我需要更好的数据结构？

更具体地说，我需要一个 Java 实现的类似于 Fibonacci 堆的东西。http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm。这是否可行？

- Rohit Banga

---

如果您感兴趣，我在Java中有一个斐波那契堆实现。它可以在线获取，网址为http://www.keithschwarz.com/interesting/code/?dir=fibonacci-heap。希望能对您有所帮助！ - templatetypedef

即使是斐波那契堆在面对元素权重的带外变化时也不具有弹性。我认为在修改元素之前需要将其删除，之后再重新插入。 - Mike Samuel

从堆中删除任意元素可能需要 O(n) 的堆构建。 - Rohit Banga

我猜问题在于PriorityQueue提供了一个线性时间的remove操作。如果数据结构足够透明，我可以外部维护优先队列中所有元素的索引，这样我就可以在O(lg V)时间内实现DECREASE-KEY操作。有没有人看到其他的数据结构可以帮助我实现这个？ - Rohit Banga

有没有人有想法，我们如何使用Java Collections API获得高效的实现？ - Rohit Banga

请参见https://dev59.com/O3I-5IYBdhLWcg3wZ3jC。 - Raedwald

Answer 1

您可以使用允许重复元素的自定义树来替代堆。 更简单的方法是，您可以使用 TreeMap<PriorityKey, LinkedHashSet<Value>>。 所有操作的时间复杂度为 O(log priorityType)：

• 添加操作为 get(priority).add(value)，如果 get 返回 null，则执行 put(priority, new LinkedHashSet())
• 删除任意元素类似，但需要在 Set 为空时从映射中删除优先级。
• poll() 是

--

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;

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

- bestsss

---

好的...所以我会说Java中的PriorityQueue既不实现DecreaseKey操作，也没有提供一种有效地让用户实现它的方式。 - Rohit Banga

@iamrohitbanga，在堆中查找键是O(n)，然后您可以删除/添加，这是(log N)。如果您需要访问队列中的随机元素，则最好使用树。 - bestsss

Answer 2

也许NavigableMap适合您的需求：易于识别“最高”或“最低”的元素，快速插入和访问时间，并且您可以轻松更新值。

http://docs.oracle.com/javase/7/docs/api/java/util/NavigableMap.html

TreeMap实现了NavigableMap接口，因此提供了firstEntry/lastEntry等许多方法。

- Olivier Croisier

---

在地图中不能有重复元素，并且必须按优先级排序。使用树（映射）的解决方案涉及将优先级->集合进行映射。（我发布的内容） - bestsss