How to iterate over a priority queue in Python?
I am trying to implement Uniform-cost search in python and for this I need a priority queue which I am using queue.py from the standard library. However, the end of the algorithm checks if there is any higher cost path in the queue. How can I check if there is any given value in my queue if it is not repeating?
thank
source to share
queue.PriorityQueue
is actually implemented with list
, and the methods put
/ get
use heapq.heappush
/ heapq.heappop
to maintain the order of precedence internally list
. So, if you want to, you can just loop over the inner list that is contained in the attribute 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')]
source to share
PriorityQueue
is implemented as a binary heap which is implemented using list
(array) in python. To iterate over a queue, you need to know the rules about where the children are stored in the list.
The rules are that all nodes have two children, unless they are the last node to have children, in which case they can have one child. All nodes that appear after the last node to have children will have zero children (duh).
A node's children are stored according to the node's own position in the list. Where i
is the index of the nodes in the list, then its children are stored at:
-
2 * i + 1
-
2 * i + 2
However, the only requirement of the heap is that all children of a node have a value greater than or equal to the value of node (or greater than depending on the implementation).
For example, on the binary heap wiki page above, you will find the following image. The first item in the queue is the root. Absolutely obvious. The second element is the largest of the root children. However, the third element can be either the remaining node of the root node, or any of the children of the second node in the queue. That is, the third item in the queue (25) could be in the same position as 19 or 1.
Thus, to iterate in turn, you need to keep track of all the currently "visible" nodes. For example:
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)
This method can be defused on queue.PriorityQueue
if you are feeling lazy, but I would advise you to implement your own priority queue class using a module heapq
as it PriorityQueue
comes with a lot of redundant functionality (basically it is a thread safe which is almost certainly not needed). It should be noted that the above method is not thread safe. If another thread modifies the queue while it is iterating, then the above method will start giving wrong numbers, and if you're lucky, it might throw an exception.
source to share
If you don't care about the thread safety it queue.queue
provides, as it is mainly for queuing up threads and not as a general purpose queue, you might be better off using collections.deque
as they are repetitive.
source to share