[Python-checkins] python/dist/src/Lib heapq.py,1.21,1.22

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