[Python-ideas] Adding a thin wrapper class around the functions in stdlib.heapq

Nick Coghlan ncoghlan at gmail.com
Wed Nov 22 23:05:05 EST 2017

On 22 November 2017 at 11:00, Chris Angelico <rosuav at gmail.com> wrote:

> So the question is more: why, with Python being the way it is, do the
> heap functions operate on a list? I think heapq.heapify is the answer:
> in linear time, it heapifies a list *in place*.
> I don't think there's any reason to have *both* interfaces to the heap
> functionality, but it certainly isn't illogical to try to treat a heap
> as a thing, and therefore have a Heap type.

Right, the parallel here is that we have a "heapq" module for the same
reason that we have list.sort(), sorted(), and the bisect module, rather
than a single "SortedList" type.
https://code.activestate.com/recipes/577197-sortedcollection/ then provides
an example of how to combine those into a "SortedCollection" type.

That said, I'm still in favour of adding an object-oriented wrapper to
either `collections` or the `heapq` module for all the classic OO reasons:

- it makes it easier to reliably maintain the heap invariant (just drop
your list reference after passing it to the heap wrapper)
- it gives both human readers and static code analysers more information to
work with ("this is a heap" rather than "this is a list")
- it provides a hook for improved interactive help on heap instances

I don't have any great concerns about potential confusion - the OO wrapper
will be easy enough to use that anyone that's unsure will likely gravitate
towards that, while the lower level `heapq` functions will remain available
for folks writing their own heap implementations.

This effect would likely be even more pronounced if the OO wrapper were
made available as `collections.Heap` (`collections` already imports the
`heapq` module for use in the Counter implementation).


Nick Coghlan   |   ncoghlan at gmail.com   |   Brisbane, Australia
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-ideas/attachments/20171123/0ec920a8/attachment.html>

More information about the Python-ideas mailing list