首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >如何遍历优先级队列?

问如何遍历优先级队列?
EN

Stack Overflow用户
提问于 2014-09-13 21:57:04
回答 3查看 16.4K关注 0票数 6

我正在尝试用Python语言实现Uniform-cost search,为此,我需要一个优先级队列,我使用标准库中的queue.py。但是,算法的末尾会检查队列中是否有任何开销更高的路径。如果队列不可迭代,我如何检查队列中是否有给定值?

EN

回答 3

Stack Overflow用户

发布于 2014-09-14 00:25:10

queue.PriorityQueue实际上是使用list实现的,put/get方法使用heapq.heappush/heapq.heappop来维护该list中的优先顺序。因此,如果您愿意,可以只迭代内部列表,该列表包含在queue属性中:

代码语言:javascript
复制
>>> from queue import PriorityQueue
>>> q = PriorityQueue()
>>> q.put((5, "a"))
>>> q.put((3, "b"))
>>> q.put((25, "c"))
>>> q.put((2, "d"))
>>> print(q.queue)
[(2, 'd'), (3, 'b'), (25, 'c'), (5, 'a')]
票数 11
EN

Stack Overflow用户

发布于 2014-09-14 01:39:32

PriorityQueue被实现为binary heap,它是使用Python中的list (数组)实现的。要遍历队列,您需要知道有关子项在列表中存储位置的规则。

规则是所有节点都有两个子节点,除非它们是最后一个具有子节点的节点,在这种情况下,它们可能只有一个子节点。在最后一个具有子节点的节点之后出现的所有节点都将有零子节点(duh)。

节点的子节点相对于该节点在列表中自己的位置进行存储。其中i是列表中节点的索引,那么它的子节点存储在:

  • 2 * i + 1
  • 2 * i + 2

但是,堆的唯一要求是一个节点的所有子节点的值必须大于或等于该节点的值(或者根据实现的不同而大于)。

例如,在上面关于二进制堆的链接维基页面中,你会发现下面的图片。队列中的第一项是根。很明显。第二项是根的子项中较大的一个。但是,第三项可以是根节点的剩余节点,也可以是队列中第二个节点的任何一个子节点。也就是说,队列(25)中的第三项可能已经处于与19或1相同的位置。

​

​

因此,要遍历队列,您需要跟踪所有当前“可见”的节点。例如:

代码语言:javascript
复制
def iter_priority_queue(queue):

    if queue.empty():
        return

    q = queue.queue
    next_indices = [0]
    while next_indices:
        min_index = min(next_indices, key=q.__getitem__)
        yield q[min_index]
        next_indices.remove(mix_index)
        if 2 * min_index + 1 < len(q):
            next_indices.append(2 * min_index + 1)
        if 2 * min_index + 2 < len(q):
            next_indices.append(2 * min_index + 2)

如果你觉得懒惰,这个方法可以用猴子补丁到queue.PriorityQueue上,但我建议你使用heapq模块实现你自己的priority queue类,因为PriorityQueue附带了很多额外的功能(主要是线程安全,几乎肯定不需要)。应该注意的是,上面的方法是的,而不是线程安全的。如果另一个线程在队列被迭代时修改了它,那么上面的方法将开始产生错误的数字,如果你幸运的话,它可能会产生一个异常。

票数 4
EN

Stack Overflow用户

发布于 2014-09-13 22:19:00

除非您需要queue.queue提供的线程安全性,因为它主要用作线程安全的作业队列,而不是通用队列,否则您最好直接使用collections.deque,因为它们是可迭代的。

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

https://stackoverflow.com/questions/25823905

复制
相关文章

相似问题

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