[Python-ideas] Higher leavel heapq

[Joao S. O. Bueno]

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?

What do you say?

http://stackoverflow.com/questions/8875706/python-heapq-with-custom-compare-predicate/8875823#8875823

js
-><-
_______________________________________________
Python-ideas mailing list
Python...@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

[Guido van Rossum]

Well, it's a lot of overhead for a very small bit of convenience. I say let's not do this, it would just encourage people to settle for a slower version. Not everything needs to be OO, you know!

--

--Guido van Rossum (python.org/~guido)

[Andrew Barnert via Python-ideas]

On Jan 14, 2016, at 08:06, Joao S. O. Bueno <jsb...@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?