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 ...