Guido van Rossum | 0b19178 | 2002-08-02 18:29:53 +0000 | [diff] [blame] | 1 | """Unittests for heapq.""" |
| 2 | |
| 3 | from test.test_support import verify, vereq, verbose, TestFailed |
| 4 | |
Tim Peters | 28c2552 | 2002-08-02 21:48:06 +0000 | [diff] [blame] | 5 | from heapq import heappush, heappop, heapify |
Guido van Rossum | 0b19178 | 2002-08-02 18:29:53 +0000 | [diff] [blame] | 6 | import random |
| 7 | |
| 8 | def check_invariant(heap): |
| 9 | # Check the heap invariant. |
| 10 | for pos, item in enumerate(heap): |
Tim Peters | d2cf1ab | 2002-08-02 19:41:54 +0000 | [diff] [blame] | 11 | if pos: # pos 0 has no parent |
| 12 | parentpos = (pos-1) >> 1 |
Guido van Rossum | 0b19178 | 2002-08-02 18:29:53 +0000 | [diff] [blame] | 13 | verify(heap[parentpos] <= item) |
| 14 | |
| 15 | def test_main(): |
| 16 | # 1) Push 100 random numbers and pop them off, verifying all's OK. |
| 17 | heap = [] |
| 18 | data = [] |
| 19 | check_invariant(heap) |
| 20 | for i in range(256): |
| 21 | item = random.random() |
| 22 | data.append(item) |
| 23 | heappush(heap, item) |
| 24 | check_invariant(heap) |
| 25 | results = [] |
| 26 | while heap: |
| 27 | item = heappop(heap) |
| 28 | check_invariant(heap) |
| 29 | results.append(item) |
| 30 | data_sorted = data[:] |
| 31 | data_sorted.sort() |
| 32 | vereq(data_sorted, results) |
| 33 | # 2) Check that the invariant holds for a sorted array |
| 34 | check_invariant(results) |
| 35 | # 3) Naive "N-best" algorithm |
| 36 | heap = [] |
| 37 | for item in data: |
| 38 | heappush(heap, item) |
| 39 | if len(heap) > 10: |
| 40 | heappop(heap) |
| 41 | heap.sort() |
| 42 | vereq(heap, data_sorted[-10:]) |
Tim Peters | 28c2552 | 2002-08-02 21:48:06 +0000 | [diff] [blame] | 43 | # 4) Test heapify. |
| 44 | for size in range(30): |
| 45 | heap = [random.random() for dummy in range(size)] |
| 46 | heapify(heap) |
| 47 | check_invariant(heap) |
| 48 | # 5) Less-naive "N-best" algorithm, much faster (if len(data) is big |
| 49 | # enough <wink>) than sorting all of data. However, if we had a max |
| 50 | # heap instead of a min heap, it would go much faster still via |
| 51 | # heapify'ing all of data (linear time), then doing 10 heappops |
| 52 | # (10 log-time steps). |
| 53 | heap = data[:10] |
| 54 | heapify(heap) |
| 55 | for item in data[10:]: |
| 56 | if item > heap[0]: # this gets rarer and rarer the longer we run |
| 57 | heappush(heap, item) |
| 58 | heappop(heap) |
| 59 | heap.sort() |
| 60 | vereq(heap, data_sorted[-10:]) |
Guido van Rossum | 0b19178 | 2002-08-02 18:29:53 +0000 | [diff] [blame] | 61 | # Make user happy |
| 62 | if verbose: |
| 63 | print "All OK" |
| 64 | |
| 65 | if __name__ == "__main__": |
| 66 | test_main() |