A note on heapq module

[bearophileHUGS]

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(sel f, item):
return heapreplace(sel f.h, item)
def clear(self):
del self.h[:]
def __contains__(se lf, 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(othe r, Heap) and self.h == other.h
def __ne__(self, other):
return not isinstance(othe r, Heap) or self.h != other.h
def __len__(self):
return len(self.h)
def __nonzero__(sel f):
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

[Steven Bethard]

be************@ lycos.com wrote:

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.

I know I've had similar bugs in my code before.

from heapq import heapify, heappush, heappop, heapreplace

class Heap(object):

[snip implementation]

+1 for adding a Heap object like this to the collections module. If you
can make a little time to add some tests (you could probably steal a lot
of what you need from test_heapq.py) you should definitely submit it as
a patch for 2.6.

STeVe

[bearophileHUGS]

I think the sort has to be simplified, otherwise it can't keep the heap
invariant...

def sort(self):
self.h.sort()

Bye,
bearophile

[Jussi Salmela]

be************@ lycos.com kirjoitti:

I think the sort has to be simplified, otherwise it can't keep the heap
invariant...

def sort(self):
self.h.sort()

Bye,
bearophile

And __repr__ should be something like this:
=========
def __repr__(self):
if self.h:
return "Heap(%s)" % self.h
else:
return "Heap()"
==========
to make it compatible with versions earlier than 2.5

Cheers,
Jussi

[Scott David Daniels]

be************@ lycos.com wrote:

In few minutes I have just written this quite raw class, ....

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:

class Heap(object):
...
def sort(self, cmp=None, key=None):
self.h.sort(cmp =cmp, key=key)

I'd remove this method.

...
def __eq__(self, other):
return isinstance(othe r, Heap) and self.h == other.h

return isinstance(othe r, self.__class__) and sorted(
self.h) == sorted(other.h)

def __ne__(self, other):
return not isinstance(othe r, Heap) or self.h != other.h

return not isinstance(othe r, self.__class__) and sorted(
self.h) != sorted(other.h)

...
def __str__(self):
return str(self.h)

return str(sorted(self .h))

def __repr__(self):
return "Heap(%s)" % self.h if self.h else "Heap()"

return "%s(%s)" % (self.__class__ .__name__, sorted(self.h))
And I'd add:
def __lt__(self, other):
raise TypeError('no ordering relation is defined for %s'
% self.__class__. __name__)
__gt__ = __le__ = __ge__ = __lt__

--Scott David Daniels
sc***********@a cm.org

[Scott David Daniels]

Scott David Daniels wrote:

Sorry, I blew the __ne__:

> def __ne__(self, other):
return not isinstance(othe r, Heap) or self.h != other.h

return not isinstance(othe r, self.__class__) and sorted(
self.h) != sorted(other.h)

Should be:
return not isinstance(othe r, self.__class__) or sorted(
self.h) != sorted(other.h)

--Scott David Daniels
sc***********@a cm.org

[bearophileHUGS]

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(sequ ence, self.__class__) :
self._heap = sequence._heap[:]
else:
if inplace and isinstance(sequ ence, list):
self._heap = sequence
else:
self._heap = list(sequence)
heapify(self._h eap)

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

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

Is this good? I think this can be accepted.

Thank you,
bye,
bearophile

[Antoon Pardon]

On 2007-01-16, be************@ lycos.com <be************ @lycos.comwrote :

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

[ Heap class based on heapq ]

For me, your class has the same drawback as the heappush, heappop
procedurers: no way to specify a comparision function. Somewhere
in my experimental code I work with line segments in two dimensions.
Now in one place I want from the available segments the one in which the
first point is farthest to the left. In a second place I want from the
available segments the one in which the second point is farthest to the
left. Both can be done with a heap, but currently I can't get both
behaviours while using the same class and using the heapq module or
your Heap class.

--
Antoon Pardon

[Neil Cerutti]

On 2007-01-16, be************@ lycos.com
<be************ @lycos.comwrote :

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.deq ue 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_q ueue 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

[Steven Bethard]

Antoon Pardon wrote:

For me, your class has the same drawback as the heappush, heappop
procedurers: no way to specify a comparision function.

Agreed. I'd love to see something like ``Heap(key=my_k ey_func)``.

STeVe