Python Cookbook

Modeling a Priority Queue

Credit: Sébastien Keim

Problem

You need a container that lets you specify the relative order of the data by priority (i.e., a priority queue).

Solution

The bisect module, from the standard Python library, is very handy for maintaining a sorted list:

import bisect

class PriorityQueue:
    def _ _init_ _(self):
        self.queue = []
    def insert(self, data, priority):
        """ Insert a new element in the queue according to its priority. """
        bisect.insort(self.queue, (priority, data))
    def pop(self):
        """ Pop the highest-priority element of the queue. """
        return self.queue.pop(  )[1]

if _ _name_ _=='_ _main_ _':  # Run a test/example when run as a script:
    a=PriorityQueue(  )
    a.insert('L',5)
    a.insert('E',4)
    a.insert('L',5)
    a.insert('O',8)
    a.insert('H',1)

    for i in range(5):
          print a.pop(),
    print

Discussion

This kind of container is generally implemented with binary trees. Since Python does not support binary trees in its standard library, I’ve used an ordered list instead, which the bisect standard module supports. If you have a great need for performance, you should have a look at the Vaults of Parnassus (http://www.vex.net/parnassus/apyllo.py?find=tree). The Vaults, always a good place to start searching for Pythonic stuff, contain several Python modules and C extensions that define binary trees and similar data structures.

The key to the recipe’s functioning is the insort function of the bisect standard module. insort must be called with a first argument that is a currently sorted list and an arbitrary second argument. The function inserts the second argument in the list so that the list remains sorted, and does so in logarithmic (O(log(N))) time. Here, we insert the pair (priority, data). Since pairs (and other tuples, lists, and sequences in general) are compared lexicographically, this means that data will be placed in increasing order of priority. Therefore, the pop function, by getting (and removing, via the lists’ pop method) the last item in list self.queue, is assured to get the item with the highest priority among those currently in the queue. It then applies indexing [1] to throw the priority away and return only the data.

See Also

Documentation on the bisect module in the Library Reference.