priority queue

[Nick Perkins]

I need a priority queue, but I am not sure what kind I should use.  I will
be doing insertions that will likely fall somewhere in the middle, and will
only be removing from the front of the queue.  I expect insertions to
out-number removals by about 2 or 3 to one.

The easy way would be to just have a list, and .sort() it at each insertion.
This, i am sure, would not be the fastest way.

I think that a heap would best suit my needs.
I could code one myself, but it must have been done before.
I can't find one in the cookbook, or the vaults!


(optional extra info)..
I am re-coding into Python a C program that I wrote which finds the shortest
solution to 'sokoban' puzzles.  It uses an A* search.  I think that the ease
of implementing heuristics and algorithms in Python will allow me to write a
'smarter' program than the C version.  In AI, smarter algorithms can give a
performance boost of many orders of magnitude, which I hope will overwhelm
any mere constant factor in speed penalty for going from C to Python.