更新元素后重新初始化java.util.PriorityQueue

我有一个包含对某些对象的引用的PriorityQueue。当我最初将元素插入优先队列时，排序由数据结构维护。现在，在删除操作之后，我更新了一些由优先级队列保存的引用。理想情况下，这需要对优先级队列进行重新组合，但显而易见，因为我在外部修改选定的引用，因此不能触发重新组合。那么确保我能够像修改队列中的任意元素一样快速提取最大值的堆的优点，最好的方法是什么？我看到我需要一个更好的数据结构？更新元素后重新初始化java.util.PriorityQueue

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

来源

2011-12-29 Rohit Banga

如果你有兴趣，我有一个Java中的斐波那契堆的实现。它可以在http://www.keithschwarz.com/interesting/code/?dir=fibonacci-heap在线获得。希望能帮助到你！ – templatetypedef 2011-12-29 03:43:02

即使斐波那契堆在面对元素权重的带外变化时也不具有弹性。我认为你需要在修改之前删除一个元素，然后重新插入它。 – 2011-12-29 04:46:16

从堆中移除任意元素将需要O（n）堆构造，我猜。 – 2011-12-29 05:17:51

你可以使用自己的树，允许重复元素而不是堆。虽然更容易，但您可以使用TreeMap<PriorityKey, LinkedHashSet<Value>>。所有操作都是O（日志priorityType）：

将是get(priority).add(value)，如果得到返回null，put(priority, new LinkedHashSet())
移除任意一个元素是相似的，除了需要去除优先出来的图，如果设置为空。
轮询（）是

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;

不过，如果你需要改变你必须删除，并添加元素的优先级。

来源

2012-02-01 23:34:41 bestsss

OK ...所以我要说的是时Queue在Java中没有实现DecreaseKey操作也不为用户提供了一种有效实施的方法。 – 2012-02-05 20:04:09

@iamrohitbanga，在堆中找到一个关键字是O（n），那么你可以删除/添加它是（log N），如果你需要访问队列中的随机元素，你会更适合用树。 – bestsss 2012-02-05 21:13:11

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

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

TreeMap中实现的NavigableMap，并且因此提供了firstEntry的/ lastEntry方法，等等。

来源

2012-02-07 17:18:52

你不能在地图中有重复的元素，它必须按优先级排序。使用树（地图）的解决方案涉及映射priority-> collection。（我发布的） – bestsss 2012-02-08 09:55:34

更新元素后重新初始化java.util.PriorityQueue

回答

相关问题