[Python-Dev] Priority queue (binary heap) python code

Kevin O'Connor kevin@koconnor.net
Tue, 25 Jun 2002 18:07:59 -0400

On Tue, Jun 25, 2002 at 02:52:03AM -0400, Oren Tirosh wrote:
> > Any chance something like this could make it into the standard python
> > library?  It would save a lot of time for lazy people like myself.  :-)
> A sorted list is a much more general-purpose data structure than a priority
> queue and can be used to implement a priority queue. It offers almost the same 
> asymptotic performance:

Hi Oren,

I agree that some form of a balanced tree object would be more useful, but
unfortunately it doesn't exist natively.  A pure python implementation of
heaps is a pretty straight-forward addition.

If, however, one were to consider adding C code then I would agree a tree
object would be more valuable.  As you surmised later, I wouldn't have
bothered with a heap if trees were available.

In fact, I've always wondered why Python dictionaries use the hash
algorithm instead of the more general binary tree algorithm.  :-}


 | Kevin O'Connor                     "BTW, IMHO we need a FAQ for      |
 | kevin@koconnor.net                  'IMHO', 'FAQ', 'BTW', etc. !"    |