(Top posting and incorrect quoting corrected.) On Sun, 29 Mar 2009 16:48:53 +0800, apollo wrote: > > as we all known, in the standard module 'heapq', we can easily get > > the smallest item from the heap. i.e. it's an implementation of > > min-heap. > > > > my question is how to use 'heapq' to extract the biggest item from the > > heap? is it possible? > > > > thanks in advance.:) > > if the 'heapq' module supports user-defined comparasion, this problem > will be much easier.
It certain does. Here's one way of turning the min-heap into a fake max- heap: >>> class Backwards(float): ... def __lt__(self, other): ... return not float.__le__(self, other) ... def __le__(self, other): ... return not float.__lt__(self, other) ... def __gt__(self, other): ... return not float.__ge__(self, other) ... def __ge__(self, other): ... return not float.__gt__(self, other) ... >>> x, y = Backwards(27), Backwards(1270) >>> x > y True >>> y < x True >>> heap = [] >>> for x in xrange(20): ... heapq.heappush(heap, Backwards(x)) ... >>> heapq.heappop(heap) 19.0 >>> heapq.heappop(heap) 18.0 >>> heap [17.0, 16.0, 13.0, 15.0, 8.0, 10.0, 12.0, 9.0, 14.0, 2.0, 7.0, 1.0, 5.0, 4.0, 11.0, 0.0, 6.0, 3.0] The problem with this approach is that when you pop the "largest" item, and compare it to something else, it will compare *smaller* because of the custom comparisons, so now you have to remove the custom comparisons to revert to the standard behaviour. The book-keeping for this could be awful. However, another approach is to use the nlargest function: >>> heap = [] >>> for i in (5, 6, 7, 0, 1, 10, 2, 4, 3, 9, 8): ... heapq.heappush(heap, i) ... >>> heap [0, 1, 2, 3, 5, 10, 7, 6, 4, 9, 8] >>> heapq.nlargest(1, heap) [10] The problem with this is that the value is not popped off the heap. Also, I'm not sure how efficient nlargest is. -- Steven -- http://mail.python.org/mailman/listinfo/python-list
