如何迭代Python中的优先级队列？

Question

我正在尝试在python中实现统一成本搜索,为此我需要一个优先级队列,我正在使用标准库中的queue.py.但是,算法结束时会检查队列中是否存在成本较高的路径.如果不可迭代,如何检查队列中是否有任何给定值？

谢谢

Answer 1

queue.PriorityQueue实际上是使用a实现的list,而put/ getmethods使用heapq.heappush/ heapq.heappop来维护其中的优先级排序list.因此,如果您愿意,您可以迭代内部列表,该列表包含在queue属性中:

>>> 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')]

Answer 2

它PriorityQueue被实现为二进制堆，在Python中使用list（数组）来实现。要迭代队列，您需要了解有关子项在列表中存储位置的规则。

规则是所有节点都有两个子节点，除非它们是最后一个有子节点的节点，在这种情况下它们可能有一个子节点。最后一个有子节点之后出现的所有节点都将有零个子节点（废话）。

节点的子节点的存储与节点自身在列表中的位置相关。i列表中节点的索引在哪里，然后它的子节点存储在：

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

但是，堆的唯一要求是节点的所有子节点的值都大于或等于该节点的值（或大于，具体取决于实现）。

例如，在上面链接的有关二进制堆的 wiki 页面中，您将找到下图。队列中的第一项是根。非常明显。第二项是根的子项中较大的一项。但是，第三项可以是根节点的剩余节点，也可以是队列中第二个节点的子节点。也就是说，队列 (25) 中的第三个项目可能与 19 或 1 处于相同的位置。

因此，要迭代队列，您需要跟踪所有当前“可查看”的节点。例如：

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因为PriorityQueue它带有很多多余的功能（主要是它是线程安全的，这几乎肯定不会）需要）。需要注意的是，上面的方法不是线程安全的。如果另一个线程在迭代队列时修改队列，那么上述方法将开始产生错误的数字，如果幸运的话，它可能会产生异常。

Answer 3

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