标签: priority-queue

哪个实现不那么"重":PriorityQueue或排序的LinkedList(使用Comparator)？

我希望对所有项目进行排序.插入将是非常频繁和偶尔我将必须运行所有列表来进行一些操作.

我想使用C++ STL priority_queue容器适配器实现计时器排队系统.

我的问题是我偶尔会取消一个计时器,但没有接口可以让我轻松删除priority_queue中不是顶级项目的项目.

有什么建议？.

谢谢您的帮助.

我正在寻找一个具有附加要求的优先级队列,一个查找/搜索功能,它将告诉一个项目是否在队列中的任何位置.所以函数将是:insert,del-min和find.

我不确定是否应该使用Heap或Self-balancing二进制搜索树.看来PQ通常用Heap实现,但我想知道使用二叉搜索树是否有任何优势,因为我还需要find函数.

此外,平均而言,我会做更多的插入而不是删除.我也在考虑一个d-ary堆.基本上,每一秒都很重要.

谢谢!

根据http://en.wikipedia.org/wiki/Heap_%28data_structure%29#Comparison_of_theoretic_bounds_for_variants,它采用Θ(logn)(转换为O(logn))来执行减小键操作.但是,似乎没有包含具有减少键操作的二进制堆实现的站点.

因此,由于Web上缺少实现,是否可以在二进制堆中执行reduce-key操作？

在阅读Guido 使用Python在2MB内存中对一百万个32位整数进行排序后,我发现了该heapq模块,但这个概念对我来说非常抽象.

一个原因是我完全不理解堆的概念,但我确实理解Guido如何使用它.

现在,除了他有点疯狂的例子,你会用什么heapq模块？

它必须始终与排序或最小值相关吗？它只是你使用的东西,因为它比其他方法更快？或者你可以做一些你不能没有的优雅事物吗？

是否存在并发可变优先级队列？理想情况下,我正在寻找一个C++实现,但是,对于初学者来说,指向算法的指针会非常有用.

要清楚,我正在寻找一个优先级队列,我可以调整元素的优先级.特别是,TBB concurrent_priority_queue不提供必要的功能.(就此而言,priority_queue即使我们忽略并发性,STL也不会.)Boost.Heap库提供了我想要的串行功能,但没有并发性.当然,我正在寻找比在每次操作中锁定整个队列更细粒度的东西.

我正在尝试在Scala(版本2.10)中实现A*搜索,但我遇到了一堵砖墙 - 我无法弄清楚如何使用Scala的优先级队列.这似乎是一个简单的任务,但在Google上搜索没有发现任何东西(除了在2.8版本中停止工作的单个代码示例)

我有一组由(Int, Int)s 表示的正方形,我需要用Ints 表示的优先级插入它们.在Python中它很简单,因为你只有一个键值对的列表,并使用heapq函数对它进行排序.但看起来Scala的元组甚至不具有可比性.

那你怎么做的？鉴于它应该是多么简单,我对完全缺乏在线信息感到惊讶.

我试图用最少的策略在Haskell中编写负载均衡器(部分是为了好玩......).我需要一个优先级队列,其中只需要以下操作"快速":

• 读取最小键
• +1最小密钥
• -1在任何键上

如果我有一个带指针的命令式语言,我可能会带来:

Head
  |
Priority 0 -> Item <-> Item <-> Item <-> Item
  |
Priority 1 -> Item <-> Item
  |
Priority 4 -> Item <-> Item <-> Item

优先级使用双向链表连接,每个优先级的项目也是如此.每个都Item包含指向头部优先级的链接.这种结构会有复杂性:

• O(1)用于读取最小键 - 从头部队列中取出
• O(1)for +1 - 删除第一优先级下的第一个项目,将其插入较低级别(可能创建一个新级别)
• O(1)为-1 - 如果我们有一个指向该项的指针,我们可以立即访问优先级,从双向链表中删除该项并将其插入另一个

是否存在一些行为大致相同的(功能？)数据结构？物品数量最多约为几百个.

我正在寻找一个在Delphi中实现的优先级队列,它在多线程环境中运行良好.

理想情况下无锁,或设计用于多线程插入/删除,其中包含比单线程实现(我已经拥有)的锁定包装更好的东西.

特殊性在于,在正常操作中,当顶部(最高优先级项)改变时,将仅存在添加,删除和通知,而最高优先级项的"弹出"操作应该非常罕见.

它将用于监视/超时线程监视任务,在其他线程中执行,这些任务预计在大多数时间内正常终止,因此它们只是从队列中添加/删除.超时线程基本上会等待下一个超时事件,因此在最高优先级事件发生更改时需要通知.

任务由脚本处理,可以随时安全地终止.

如果有比这更好的算法而不是优先级队列,它们也可能是很好的答案!

编辑:在Martin James的评论之后,另一个特点是相对较少的不同超时值,并且对于每个超时值,问题变成FIFO队列的问题.

最相似的容器有会员类型,如key_compare或value_compare但有没有为priority_queue.

是因为priority_queue是适配器吗？或者这是错误的标准？