[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
--
------------------------------------------------------------------------
| Kevin O'Connor "BTW, IMHO we need a FAQ for |
| kevin@koconnor.net 'IMHO', 'FAQ', 'BTW', etc. !" |
------------------------------------------------------------------------