[Python-ideas] Higher leavel heapq

Andrew Barnert abarnert at yahoo.com
Thu Jan 14 11:54:50 EST 2016


On Jan 14, 2016, at 08:06, Joao S. O. Bueno <jsbueno at python.org.br> wrote:
> 
> Hi,
> 
> the heapq stdlib module is really handy, but a little low level -
> in that it accepts a sequence, possibly only a list, as the heap-object,
> and that object have to be handled independently, outside the functions
> provided in there. (One can't otherwise insert or delete elements of that list,
> without destroying the heap, for example).
> 
> It would be simple to have a higher level class that would do just
> that, and simplify the use
> of an ordered container - what about having an extra class there?
> 
> I have the snippet bellow I wrote on stack-overflow a couple years ago -
> it is very handy.With a little more boiler plate and code hardening,
> maybe it could
> be a nice thing for the stdlib?

Using (key(x), x) as the elements doesn't work if the real values aren't comparable, and isn't stable even if they are. So, to make this work fully generally, you have to add a third element, like (key(x), next(counter), x). But when that isn't necessary, it's pretty wasteful.

Also, for many uses, the key doesn't have anything to do with the values--e.g., a timer queue just uses the insertion time--so the sorting-style key function is misleading.

Also, a heap as a collection-like data structure isn't that useful on its own. There are a variety of iterative algorithms that use a heap internally, but they don't need to expose it to callers. (And most of the common ones are already included in the module.) And there are also a variety of data structures that use a heap internally, but they also don't need to expose it to callers. For example, read the section in the docs on priority queues, and try to implement a pqueue class on top of your wrapper class vs. directly against the module functions. And do the same with then nlargest function (you can find the source linked from the docs). In both cases, the version without the class is more readable, less code, and likely more efficient, and the API for users is the same, so what has the wrapper class bought you?


More information about the Python-ideas mailing list