[Python-Dev] Re: heapq method names

[Tim Peters]

[Jeremy Hylton]
> You can't use all of the regular list methods, right?  If I'd called
> append() an a Heap(), it wouldn't maintain the heap invariant.  I
> would think the same is true of insert() and lots of other methods.

Well, you *can* use all list methods, just as you can already call
heapq.heappop and pass any old list.  heapify exists so that you can repair
the heap invariant if you have reason to believe you may have broken it.

> If we add a Heap class, which seems quite handy, maybe we should
> disable methods that don't work.

If it were called PriorityQueue, definitely, but "a heap" is a specific
implementation and heap users can exploit the list representation in lots of
interesting ways.

> Interesting to note that if you disable the invalid methods of list,
> then you've got a subclass of list that is not a subtype.

It is an interesting case this way!  There's a related case that's perhaps
of more pressing interest:  Raymond Hettinger has pointed out that, e.g.,

    3 in Set

is much slower than

    3 in dict

This is because Set.__contains__ is a Python-level call.  I sped up almost
all the binary set operations yesterday by factors of 2 to 5, mostly via
just using the underlying dict.__contains__ under the covers instead of
appealing to Set.__contains__.

For "simple sets" (sets that don't magically try to convert mutable
objects-- like sets --into immutable objects), the speed of

    3 in Set

could be restored by subclassing from dict and inheriting its __contains__.
But Set is trying not to make any promises about representation, so this is
a clearer case for some form of "(only) implementation inheritance".  The
desire is driven only by speed, but that can be a legit concern too (I'm not
sure it's a killer concern in this particular case).