A note on heapq module

bearophileHUGS at lycos.com bearophileHUGS at lycos.com
Tue Jan 16 12:24:45 EST 2007


In few minutes I have just written this quite raw class, it lacks
doctring (the same of the functions of the heapq module), it may
contain bugs still, I haven't tested it much. It's just a simple
wrapper around some of the functions of the heapq module (nsmallest and
nlargest are missing). Usually I use classes only when I need then, I
like functional programming enough, and this class seems to just slow
down the functions of the heapq module. But I think an improved class
similar to this one may be useful (added, replacing isn't necessary)
into the heapq module, because it can avoid cetain errors: I know what
Heaps are and how they work, but some time ago I have written a bug
into small program that uses the functions of the heapq module, because
I have added an item to the head of the heap using a normal list
method, breaking the heap invariant. With a simple class like this one
all the methods of your object keep the heap invariant, avoiding that
kind of bugs. (If you are interested I can improve this class some,
it't not difficult.)


from heapq import heapify, heappush, heappop, heapreplace

class Heap(object):
    def __init__(self, init=None):
        if init is None:
            self.h = []
        elif isinstance(init, Heap):
            self.h = init.h[:]
        else:
            self.h = list(init)
            heapify(self.h)
    def smallest(self):
        return self.h[0]
    def sort(self, cmp=None, key=None):
        self.h.sort(cmp=cmp, key=key)
    def heappush(self, item):
        heappush(self.h, item)
    def heappop(self):
        return heappop(self.h)
    def heapreplace(self, item):
        return heapreplace(self.h, item)
    def clear(self):
        del self.h[:]
    def __contains__(self, item):
        return item in self.h
    def __hash__(self):
        raise TypeError("Heap objects are unhashable.")
    def __iter__(self):
        return self.h.__iter__()
    def __eq__(self, other):
        return isinstance(other, Heap) and self.h == other.h
    def __ne__(self, other):
        return not isinstance(other, Heap) or self.h != other.h
    def __len__(self):
        return len(self.h)
    def __nonzero__(self):
        return bool(self.h)
    def __str__(self):
        return str(self.h)
    def __repr__(self):
        return "Heap(%s)" % self.h if self.h else "Heap()"

Bye,
bearophile




More information about the Python-list mailing list