A note on heapq module

bearophileHUGS at lycos.com bearophileHUGS at lycos.com
Tue Jan 16 22:25:06 CET 2007


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):

def __init__(self, sequence=None, inplace=False):
    if sequence is None:
        self._heap = []
    elif isinstance(sequence, self.__class__):
        self._heap = sequence._heap[:]
    else:
        if inplace and isinstance(sequence, list):
            self._heap = sequence
        else:
            self._heap = list(sequence)
        heapify(self._heap)

The second thing, I don't like much the __iter__ because it yields
unsorted items:

def __iter__(self):
    return self._heap.__iter__()

Is this good? I think this can be accepted.

Thank you,
bye,
bearophile




More information about the Python-list mailing list