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