heapq - why no key= arg?

Mon Apr 27 10:24:32 EDT 2015

Neal Becker wrote:
> Looking at heapq, I see only nlargest/nsmallest provide a key= arg. What
> about other operations, such as heapify? Am I not understanding
> something? 

nlargest/nsmallest() use the decorate-sort-undecorate pattern to avoid 
calculating the key more than once. For the other operations you'd have to 
calculate key(item) repeatedly for every item involved in the specific 
operation.
> I suppose for other ops, such as heapify, I can only customize
> comparison by customizing the object comparison operators?

I'm sure someons's written a Heapq class that automatically decorates when 
an item is added and undecorates when one is looked up or removed. As I'm 
too lazy to look it up here's a sketch:
$ cat myheapq.py
import heapq
from itertools import count
class Heapq:
 def __init__(self, values, key):
 self.counter = count()
 self.key = key
 self.items = [(key(value), index, value)
 for index, value in zip(self.counter, values)]
 heapq.heapify(self.items)
 def push(self, value):
 heapq.heappush(
 self.items,
 (self.key(value), next(self.counter), value))
 def pop(self):
 return heapq.heappop(self.items)[-1]
 def __str__(self):
 return str([item[-1] for item in self.items])
 def __bool__(self):
 return not not self.items
if __name__ == "__main__":
 h = Heapq([1, -2, -3, 4], key=abs)
 print(h)
 print(h.pop())
 print(h)
 h.push(-5)
 print(h)
 while h:
 print(h.pop(), end=", " if h else "\n")
$ python3 myheapq.py 
[1, -2, -3, 4]
1
[-2, 4, -3]
[-2, 4, -3, -5]
-2, -3, 4, -5