Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #89458

Re: heapq - why no key= arg?

Show key headers only | View raw

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

Back to comp.lang.python | Previous | Next | Find similar | Unroll thread

Thread

Re: heapq - why no key= arg? Peter Otten <__peter__@web.de> - 2015-04-27 16:24 +0200

csiph-web