Path: csiph.com!usenet.pasdenom.info!weretis.net!feeder4.news.weretis.net!newsreader4.netcologne.de!news.netcologne.de!feeder1.cambriumusenet.nl!feed.tweaknews.nl!194.109.133.81.MISMATCH!newsfeed.xs4all.nl!newsfeed2a.news.xs4all.nl!xs4all!post.news.xs4all.nl!not-for-mail
To: python-list@python.org
From: Peter Otten <__peter__@web.de>
Subject: Re: heapq - why no key= arg?
Date: Mon, 27 Apr 2015 16:24:32 +0200
Organization: None
References: <mhlf3c$lba$1@ger.gmane.org>
Mime-Version: 1.0
Content-Type: text/plain; charset="ISO-8859-1"
Content-Transfer-Encoding: 7Bit
User-Agent: KNode/4.13.3
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.44.1430144702.3680.python-list@python.org>
Lines: 63
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:89458

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