A note on heapq module

Steven Bethard steven.bethard at gmail.com
Thu Jan 18 23:08:05 CET 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