|I l@ve RuBoard|
17.16 Modeling a Priority Queue
Credit: Sébastien Keim
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( ) if _ _name_ _=='_ _main_ _': # Run a test/example when run as a script: a=PriorityQueue( ) a.append('L',5) a.append('E',4) a.append('L',5) a.append('O',8) a.append('H',1) for i in range(5): print a.pop(0), print
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  to throw the priority away and return only the data.
17.16.4 See Also
Documentation on the bisect module in the Library Reference.
|I l@ve RuBoard|