On 2007-01-16, [EMAIL PROTECTED] <[EMAIL PROTECTED]> 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 -- http://mail.python.org/mailman/listinfo/python-list