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

Tim Peters tim.one@comcast.net
Wed, 26 Jun 2002 00:30:36 -0400

> Should this PEP be split in two, then?  One for a new "AbstractData"
> package (that would include the heap algorithm) and one for an update to
> Queue that would use some algorithm from AbstractData.  The latter might
> not even need a PEP.

I'm chuckling, but to myself <wink>.  By the time you add all the bells and
whistles everyone may want out of "a priority queue", the interface gets so
frickin' complicated that almost everyone will ignore the library and call
bisect.insort() themself.

/F gives me a thread-safe Queue when I don't want to pay overheads for
enforcing mutual exclusion in 99% of my priority-queue apps.  Schemes that
store (priority, object) tuples to exploit lexicographic comparison are
convenient to code but a nightmare if priorities can ever be equal, and
object comparison can raise exceptions, or object comparison can be
expensive.  Sometimes I want a min-queue, other times a max-queue.
Sometimes I need efficient access to both ends.  About a month ago I needed
to write a priority queue that was especially efficient at adding thousands
of new entries in one gulp.

And so on.  It's easier to write appropriate code from scratch in Python
than to figure out how to *use* a package profligate enough to contain
canned solutions for all common and reasonable use cases.  People have been
known to gripe at the number of methods Python's simple little lists and
dicts have sprouted -- heh heh.

BTW, the Zope BTree may be a good candidate to fold into Python.  I'm not
sure.  It's a mountain of fairly sophisticated code with an interface so
rich that it's genuinely hard to learn how to use it as intended -- the
latter especially should appeal to just about everyone <wink>.