heapq - why no key= arg?
Peter Otten
__peter__ at web.de
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
More information about the Python-list
mailing list