ActiveState Code

Recipe 87369: Priority Queue

Thread-safe priority queue using Queue.Queue

Python 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
import Queue

class PriorityQueue(Queue.Queue):
    def _put(self, item):
        data, priority = item
        self._insort_right((priority, data))
        
    def _get(self):
        return self.queue.pop(0)[1]

    def _insort_right(self, x):
        """Insert item x in list, and keep it sorted assuming a is sorted.
        
        If x is already in list, insert it to the right of the rightmost x.       
        """
        a = self.queue
        lo = 0        
        hi = len(a)
        
        while lo < hi:
            mid = (lo+hi)/2
            if x[0] < a[mid][0]: hi = mid
            else: lo = mid+1
        a.insert(lo, x)

def test():
    pq = PriorityQueue()

    pq.put(('b', 1))
    pq.put(('a', 1))
    pq.put(('c', 1))
    pq.put(('z', 0))
    pq.put(('d', 2))

    while not pq.empty():
        print pq.get(),   
    
test() # prints z b a c d

Comments

  1. 1. At 5:53 a.m. on 22 feb 2002, Lee Harr said:

    pop or get? Queue.Queue does not have a pop() method. It does however have a get() method.

  2. 2. At 5:54 a.m. on 22 feb 2002, Lee Harr said:

    output. For me, this outputs: z b a c d

  3. 3. At 3:57 a.m. on 3 may 2002, simo salminen (the author) said:

    output. typo corrected.

  4. 4. At 4:02 a.m. on 3 may 2002, simo salminen (the author) said:

    pop method. I don't quite understand what you mean. the pop() call in _get-calls the internal queue-data structure, which is python list.

  5. 5. At 3:01 p.m. on 11 jun 2002, Mark Moraes said:

    using bisect.insort_right(). Would using bisect.insort_right() cause problems? i.e.

    def _put(self, item):
    bisect.insort_right(self.queue, item)

    seems to work nicely.

    I also found a 'top' method useful:

    def top(self):
    "non-destructively return smallest element in pqueue"
    try:
        x = self.queue[0]
    except IndexError:
        x = None
    return x
  6. 6. At 8:38 p.m. on 28 oct 2002, Chris Perkins said:

    bisect.insort_right will not work. Using bisect.insort_right as you suggest would not work.

    Assuming item is a tuple of (priority, data), then it would be inserted amongst other items in the queue with the same priority, but sorted by the value of its data, rather than by its arrival time.

    You may be able to hack around this with something like:

    self.queue.insert(bisect.bisect_right(self.queue, (priority, sys.maxint)), (priority, data))

    if the data are all integers.

  7. 7. At 3:59 p.m. on 31 jan 2003, greg klanderman said:

    bisection. why bother with bisection if you're just going to use an O(n) insert?

  8. 8. At 4:19 a.m. on 5 jun 2007, Thomas Ahle said:

    Why not use a heapqueue. Like this:

    from Queue import Queue
from heapq import heappush, heappop

class PriorityQueue(Queue):
    # Initialize the queue representation
    def _init(self, maxsize):
        self.maxsize = maxsize
        self.queue = []

    # Put a new item in the queue
    def _put(self, item):
        return heappush(self.queue, item)

    # Get an item from the queue
    def _get(self):
        return heappop(self.queue)

if __name__ == "__main__":
    q = PriorityQueue()
    q.put((2,"a"))
    q.put((0,"b"))
    q.put((1,"c"))
    q.put((2,"d"))
    q.put((1,"e"))
    while not q.empty():
        print q.get()

    prints b, c, e, a, d

  9. 9. At 2:02 a.m. on 21 jun 2007, Giles Brown said:

    Using bisect module. I don't really understand the maths of heapq, but it doesn't seem to maintain the existing ordering. In fact if you use the example from the published 2nd edition cookbook, if you insert a series of items with the same time.time() value they get ordered according to their (undecorated) item value which is not so good.

    And I'm a bit bothered by not re-using the bisect algorithm, so here is a version that doesn't sort on item value, but does use the bisect module.

    from Queue import Queue
from bisect import bisect_left

class PriorityQueue(Queue):

    def _init(self, maxsize):
        self.maxsize = maxsize
        # Python 2.5 uses collections.deque, but we can't because
        # we need insert(pos, item) for our priority stuff
        self.queue = []

    def put(self, item, priority=0, block=True, timeout=None):
        """Puts an item onto the queue with a numeric priority (default is zero).

        Note that we are "shadowing" the original Queue.Queue put() method here.
        """
        Queue.put(self, (priority, item), block, timeout)

    def _put(self, item):
        """Override of the Queue._put to support prioritisation."""
        # Priorities must be integers!
        priority = int(item[0])

        # Using a tuple (priority+1,) finds us the correct insertion
        # position to maintain the existing ordering.
        self.queue.insert(bisect_left(self.queue, (priority+1,)), item)

    def _get(self):
        """Override of Queue._get().  Strips the priority."""
        return self.queue.pop(0)[1]
  10. 10. At 9:02 a.m. on 18 may 2008, David Arnold said:

    Priority Queue Semantics. Maintaining the existing ordering isn't usually what a priority queue does. If you have several objects with the same priority, it doesn't matter what order you address them in. (After all, they have the /same/ priority.) ER-style priority, like your example, is a different strategy (items that have the same value for their priority don't technically have the same 'priority'). Often, applications that require priority queues (like implementations of Dijkstra's algorithm, or A* search) would much rather have the performance boost of a heap versus the maintenance of first-come ordering. (heap is O(logN) to insert, list insort is O(NlogN))

    It's a trade-off of performance versus a specific semantic. I am curious: what situation did you create this PriorityQueue for that demanded first-come ordering?

Sign in to comment