heapq "key" arguments

[Gabriel Genellina]

En Fri, 31 Jul 2009 16:38:01 -0300, Joshua Bronson <jabronson at gmail.com>  
escribió:
> On Jul 31, 2:02 pm, Jonathan Gardner <jgard... at jonathangardner.net>  
> wrote:
>> On Jul 31, 10:44 am, Joshua Bronson <jabron... at gmail.com> wrote:

>> > Say I want to maintain a heap of (x, y) pairs sorted only by
>> > first coordinate. Without being able to pass key=itemgetter(0), won't
>> > heapifying a list of such pairs unnecessarily compare both
>> > coordinates?
>>
>> It will compare the second value only if the first values are equal.
>
> I don't see how that helps. That's not at all the same thing as being
> able to pass key=itemgetter(0).

Ok, it's not strictly the same, but usually it doesn't hurt. The heaqp  
module doesn't promise anything about equal elements: it may keep the  
original order, rearrange them at will, reverse them, whatever. So the  
element-wise comparison of tuples is as good as comparing only the first  
element - *except* when comparing the second element isn't cheap or has  
side effects or something like that. In that case, use a custom class to  
redefine comparison operators:

 from heapq import heapify, heappop

class tuplebyfirst(tuple):
     "tuple that sorts only on first element"
     def __lt__(self, other):
         return self[0]<other[0]

heap = [tuplebyfirst(x) for x in [(2, 3, 'A'), (1, 4, 'B'),
         (2, 5, 'C'), (2, 5, 'D'), (3, 0, 'E')]]
print heap
heapify(heap)
while heap:
     print heappop(heap)

Output:

[(2, 3, 'A'), (1, 4, 'B'), (2, 5, 'C'), (2, 5, 'D'), (3, 0, 'E')]
(1, 4, 'B')
(2, 5, 'C')
(2, 5, 'D')
(2, 3, 'A')
(3, 0, 'E')

The letters are just to recognize the original ordering.
(I've used an undocumented property: all heapq functions compare elements  
ONLY by using "<", in 2.6.2 at least. Defining all the other rich  
comparison methods doesn't change anything)

-- 
Gabriel Genellina