A note on heapq module

[Neil Cerutti]

On 2007-01-16, bearophileHUGS at lycos.com
<bearophileHUGS at lycos.com> wrote:
> Scott David Daniels:
>> I'd suggest some changes.  It is nice to have Heaps with equal
>> contents equal no matter what order the inserts have been
>> done. Consider how you want Heap([1, 2, 3]) and Heap([3, 1,
>> 2]) to behave. Similarly, it is nice to have str and repr
>> produce canonical representations (I would skip the __str__
>> code, myself, though). Also, subclasses should get their
>> identities tweaked as so:
>
> My version was a *raw* one, just an idea, this is a bit better:
> http://rafb.net/p/nLPPjo35.html
> I like your changes. In the beginning I didn't want to put
> __eq__ __ne__ methods at all, because they are too much slow,
> but being them O(n ln n) I think your solution is acceptable.
>
> Some methods may have a name different from the heap functions:
> def smallest(self):
> def push(self, item):
> def pop(self):
> def replace(self, item):
>
> Two things left I can see: I think the __init__ may have a
> boolean inplace parameter to avoid copying the given list, so
> this class is about as fast as the original heapify function
> (but maybe such thing is too much dirty for a Python stdlib):

One more idea, cribbed from the linked list thread elsewhere: it
might be nice if your Heap could optionally use an underlying
collections.deque instead of a list.

I don't know how excellent Python's deque is, but it's possible a
deque would provide a faster heap than a contiguous array. C++'s
std::deque is the default implementation of C++'s
std::priority_queue for that reason (unless I'm confused again).

-- 
Neil Cerutti
We will sell gasoline to anyone in a glass container. --sign at Santa Fe gas
station