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