[Python-checkins] python/dist/src/Lib heapq.py,1.21,1.22
rhettinger at users.sourceforge.net
rhettinger at users.sourceforge.net
Thu Jun 10 01:03:19 EDT 2004
Update of /cvsroot/python/python/dist/src/Lib
In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv16530/Lib
Modified Files:
heapq.py
Log Message:
SF patch #969791: Add nlargest() and nsmallest() to heapq.
Index: heapq.py
===================================================================
RCS file: /cvsroot/python/python/dist/src/Lib/heapq.py,v
retrieving revision 1.21
retrieving revision 1.22
diff -C2 -d -r1.21 -r1.22
*** heapq.py 19 Apr 2004 19:06:21 -0000 1.21
--- heapq.py 10 Jun 2004 05:03:16 -0000 1.22
***************
*** 31,35 ****
"""
! # Original code by Kevin O'Connor, augmented by Tim Peters
__about__ = """Heap queues
--- 31,35 ----
"""
! # Original code by Kevin O'Connor, augmented by Tim Peters and Raymond Hettinger
__about__ = """Heap queues
***************
*** 127,131 ****
"""
! __all__ = ['heappush', 'heappop', 'heapify', 'heapreplace']
def heappush(heap, item):
--- 127,134 ----
"""
! __all__ = ['heappush', 'heappop', 'heapify', 'heapreplace', 'nlargest',
! 'nsmallest']
!
! from itertools import islice, repeat
def heappush(heap, item):
***************
*** 169,172 ****
--- 172,204 ----
_siftup(x, i)
+ def nlargest(iterable, n):
+ """Find the n largest elements in a dataset.
+
+ Equivalent to: sorted(iterable, reverse=True)[:n]
+ """
+ it = iter(iterable)
+ result = list(islice(it, n))
+ if not result:
+ return result
+ heapify(result)
+ _heapreplace = heapreplace
+ sol = result[0] # sol --> smallest of the nlargest
+ for elem in it:
+ if elem <= sol:
+ continue
+ _heapreplace(result, elem)
+ sol = result[0]
+ result.sort(reverse=True)
+ return result
+
+ def nsmallest(iterable, n):
+ """Find the n smallest elements in a dataset.
+
+ Equivalent to: sorted(iterable)[:n]
+ """
+ h = list(iterable)
+ heapify(h)
+ return map(heappop, repeat(h, min(n, len(h))))
+
# 'heap' is a heap at all indices >= startpos, except possibly for pos. pos
# is the index of a leaf with a possibly out-of-order value. Restore the
More information about the Python-checkins
mailing list