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

[rhettinger at users.sourceforge.net]

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