首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >如何在修改队列内容后从优先级队列中获取最小元素

问如何在修改队列内容后从优先级队列中获取最小元素
EN

Stack Overflow用户
提问于 2015-06-14 13:25:00
回答 3查看 4.2K关注 0票数 2

我试图用Java语言中的priority queue来实现Dijkstra算法。不幸的是,它返回了错误的结果……我已经追踪到了这个问题。这是Problem..After将节点权重插入到队列中,我正在修改这些节点权重,但当我试图从优先级队列中删除元素时,它返回了历史最小值(插入时的最小值)。remove()不知道优先级队列已经被modified..Any帮助将非常感谢...Thanks!

注意:如果需要,我可以添加源代码

EN

回答 3

Stack Overflow用户

发布于 2015-06-14 13:31:43

This的问题应该会对你有所帮助。Java语言中PriorityQueue的缺点是,如果插入的元素值发生变化,优先级队列不会重新构建以反映新的顺序。因此,您必须删除并重新插入更改的元素,以满足您的用例。

票数 1
EN

Stack Overflow用户

发布于 2015-06-14 13:38:13

标准接口不提供更新功能。您已经使用了实现此功能的自定义类型。这是因为,正如S.O帖子中所述,标题为"Updating Java PriorityQueue when its elements change priority":

您必须删除并重新插入,因为队列的工作方式是在插入新元素时将它们放在适当的位置。

在S.O的帖子“Java Priority Queue reordering when editing elements”中讨论了这对你的影响:

优先级队列不会在添加元素或removed....Doing时重新排序所有元素,这将是非常昂贵的。PriorityQueue不提供api来通知它更改的节点,因为这将需要它提供有效的节点查找,而它的底层算法不支持。

上面的帖子提供了实现Dijsktra算法的替代方法。

如果你有任何问题请告诉我!

票数 1
EN

Stack Overflow用户

发布于 2015-06-14 13:46:33

就像Map的键一样,放在PriorityQueue中的元素需要是不可变的。将插入到PriorityQueue中的元素与PriorityQueue中的所有现有元素进行比较。因此,如果底层元素发生变化,您的PriorityQueue很可能无法保存不变量。

您可以使用的另一种数据结构是TreeSet。TreeSet的remove运算为O(lg )。

票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/30826202

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档