A note on heapq module
Steven Bethard
steven.bethard at gmail.com
Thu Jan 18 17:08:05 EST 2007
bearophileHUGS at lycos.com wrote:
> Steven Bethard:
>> Antoon Pardon:
>>> 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_key_func)``.
>
> It can be done, but the code becomes more complex and hairy:
> http://rafb.net/p/iCCmDz16.html
Cool!
The current code fails when using unbound methods however::
>>> heap = Heap()
>>> Heap.push(heap, 1)
Traceback (most recent call last):
File "<interactive input>", line 1, in <module>
AttributeError: type object 'Heap' has no attribute 'push'
I would have written the code like::
def smallest(self):
result = self._heap[0]
if self._key is not None:
result = result[2]
return result
def push(self, item):
if self._key is not None:
item = self._key(item), self._itemid, item
self._itemid += 1
heappush(self._heap, item)
def pop(self):
result = heappop(self._heap)
if self._key is not None:
result = result[2]
return result
def popn(self, n):
result = [heappop(self._heap) for _ in xrange(n)]
if self._key is not None:
result = [item[2] for item in result]
return result
def replace(self, item):
if self._key is not None:
item = self._key(item), self._itemid, item
self._itemid += 1
result = heapreplace(self._heap, item)
if self._key is not None:
result = result[2]
return result
This allows unbound methods to work, and substantially lowers the code
duplication. It does add a few extra if statements, but since they're
``is`` tests, they should be pretty fast.
STeVe
More information about the Python-list
mailing list