[Python-checkins] python/dist/src/Lib/test test_heapq.py,1.3,1.4

[tim_one@users.sourceforge.net]

Update of /cvsroot/python/python/dist/src/Lib/test
In directory usw-pr-cvs1:/tmp/cvs-serv23987/python/Lib/test

Modified Files:
	test_heapq.py 
Log Message:
Hmm!  I thought I checked this in before!  Oh well.

Added new heapify() function, which transforms an arbitrary list into a
heap in linear time; that's a fundamental tool for using heaps in real
life <wink>.

Added heapyify() test.  Added a "less naive" N-best algorithm to the test
suite, and noted that this could actually go much faster (building on
heapify()) if we had max-heaps instead of min-heaps (the iterative method
is appropriate when all the data isn't known in advance, but when it is
known in advance the tradeoffs get murkier).


Index: test_heapq.py
===================================================================
RCS file: /cvsroot/python/python/dist/src/Lib/test/test_heapq.py,v
retrieving revision 1.3
retrieving revision 1.4
diff -C2 -d -r1.3 -r1.4
*** test_heapq.py	2 Aug 2002 19:41:54 -0000	1.3
--- test_heapq.py	2 Aug 2002 21:48:06 -0000	1.4
***************
*** 3,7 ****
  from test.test_support import verify, vereq, verbose, TestFailed
  
! from heapq import heappush, heappop
  import random
  
--- 3,7 ----
  from test.test_support import verify, vereq, verbose, TestFailed
  
! from heapq import heappush, heappop, heapify
  import random
  
***************
*** 38,41 ****
--- 38,59 ----
          heappush(heap, item)
          if len(heap) > 10:
+             heappop(heap)
+     heap.sort()
+     vereq(heap, data_sorted[-10:])
+     # 4) Test heapify.
+     for size in range(30):
+         heap = [random.random() for dummy in range(size)]
+         heapify(heap)
+         check_invariant(heap)
+     # 5) Less-naive "N-best" algorithm, much faster (if len(data) is big
+     #    enough <wink>) than sorting all of data.  However, if we had a max
+     #    heap instead of a min heap, it would go much faster still via
+     #    heapify'ing all of data (linear time), then doing 10 heappops
+     #    (10 log-time steps).
+     heap = data[:10]
+     heapify(heap)
+     for item in data[10:]:
+         if item > heap[0]:  # this gets rarer and rarer the longer we run
+             heappush(heap, item)
              heappop(heap)
      heap.sort()