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