On Wed, 22 Nov 2017 17:11:53 +1100 Chris Angelico <rosuav@gmail.com> wrote:
On Wed, Nov 22, 2017 at 3:55 PM, Greg Ewing <greg.ewing@canterbury.ac.nz> wrote:
Chris Angelico 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*.
There's no reason a Heap object couldn't accomodate that case. E.g. the constructor could optionally accept an existing list to heapify and wrap.
Yeah but if it's wrapping an existing list, it's not really constructing a new object. Every other constructor in Python will make something independent of its origin (if you call list() on a list, you get back a brand new copy, for instance), but to take advantage of in-place heapification, it would have to mutate the input. I think that would be even more surprising.
In any case, copying a list a pretty cheap, so in-place heapification isn't a very important optimization. Regards Antoine.