cpython-lru_cache-weakref: Lib/heapq.py annotate

annotate Lib/heapq.py @ 79675:c0a2294de787 2.7

Issue #16199: Backport 2to3 typo fix from 3.2.

author	Chris Jerdonek <chris.jerdonek@gmail.com>
date	Thu, 11 Oct 2012 16:15:46 -0700
parents	57f73b0f921c
children	aa9ed98a49cb

rev	line source
61705 f76f81044d40 Merged revisions 68750,68811,68945,69157 via svnmerge from Georg Brandl <georg@python.org> parents: 55513 diff changeset	1 # -- coding: latin-1 --
31931 63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	2
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	3 """Heap queue algorithm (a.k.a. priority queue).
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	4
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	5 Heaps are arrays for which a[k] <= a[2k+1] and a[k] <= a[2k+2] for
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	6 all k, counting elements from 0. For the sake of comparison,
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	7 non-existing elements are considered to be infinite. The interesting
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	8 property of a heap is that a[0] is always its smallest element.
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	9
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	10 Usage:
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	11
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	12 heap = [] # creates an empty heap
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	13 heappush(heap, item) # pushes a new item on the heap
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	14 item = heappop(heap) # pops the smallest item from the heap
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	15 item = heap[0] # smallest item on the heap without popping it
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	16 heapify(x) # transforms list into a heap, in-place, in linear time
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	17 item = heapreplace(heap, item) # pops and returns smallest item, and adds
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	18 # new item; the heap size is unchanged
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	19
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	20 Our API differs from textbook heap algorithms as follows:
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	21
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	22 - We use 0-based indexing. This makes the relationship between the
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	23 index for a node and the indexes for its children slightly less
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	24 obvious, but is more suitable since Python uses 0-based indexing.
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	25
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	26 - Our heappop() method returns the smallest item, not the largest.
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	27
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	28 These two make it possible to view the heap as a regular Python list
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	29 without surprises: heap[0] is the smallest item, and heap.sort()
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	30 maintains the heap invariant!
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	31 """
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	32
32316 9e5af45cefcb SF patch #969791: Add nlargest() and nsmallest() to heapq. Raymond Hettinger <python@rcn.com> parents: 31931 diff changeset	33 # Original code by Kevin O'Connor, augmented by Tim Peters and Raymond Hettinger
31931 63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	34
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	35 __about__ = """Heap queues
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	36
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	37 [explanation by Fran�ois Pinard]
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	38
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	39 Heaps are arrays for which a[k] <= a[2k+1] and a[k] <= a[2k+2] for
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	40 all k, counting elements from 0. For the sake of comparison,
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	41 non-existing elements are considered to be infinite. The interesting
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	42 property of a heap is that a[0] is always its smallest element.
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	43
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	44 The strange invariant above is meant to be an efficient memory
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	45 representation for a tournament. The numbers below are `k', not a[k]:
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	46
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	47 0
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	48
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	49 1 2
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	50
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	51 3 4 5 6
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	52
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	53 7 8 9 10 11 12 13 14
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	54
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	55 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	56
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	57
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	58 In the tree above, each cell `k' is topping `2k+1' and `2k+2'. In
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	59 an usual binary tournament we see in sports, each cell is the winner
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	60 over the two cells it tops, and we can trace the winner down the tree
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	61 to see all opponents s/he had. However, in many computer applications
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	62 of such tournaments, we do not need to trace the history of a winner.
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	63 To be more memory efficient, when a winner is promoted, we try to
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	64 replace it by something else at a lower level, and the rule becomes
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	65 that a cell and the two cells it tops contain three different items,
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	66 but the top cell "wins" over the two topped cells.
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	67
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	68 If this heap invariant is protected at all time, index 0 is clearly
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	69 the overall winner. The simplest algorithmic way to remove it and
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	70 find the "next" winner is to move some loser (let's say cell 30 in the
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	71 diagram above) into the 0 position, and then percolate this new 0 down
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	72 the tree, exchanging values, until the invariant is re-established.
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	73 This is clearly logarithmic on the total number of items in the tree.
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	74 By iterating over all items, you get an O(n ln n) sort.
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	75
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	76 A nice feature of this sort is that you can efficiently insert new
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	77 items while the sort is going on, provided that the inserted items are
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	78 not "better" than the last 0'th element you extracted. This is
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	79 especially useful in simulation contexts, where the tree holds all
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	80 incoming events, and the "win" condition means the smallest scheduled
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	81 time. When an event schedule other events for execution, they are
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	82 scheduled into the future, so they can easily go into the heap. So, a
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	83 heap is a good structure for implementing schedulers (this is what I
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	84 used for my MIDI sequencer :-).
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	85
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	86 Various structures for implementing schedulers have been extensively
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	87 studied, and heaps are good for this, as they are reasonably speedy,
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	88 the speed is almost constant, and the worst case is not much different
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	89 than the average case. However, there are other representations which
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	90 are more efficient overall, yet the worst cases might be terrible.
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	91
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	92 Heaps are also very useful in big disk sorts. You most probably all
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	93 know that a big sort implies producing "runs" (which are pre-sorted
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	94 sequences, which size is usually related to the amount of CPU memory),
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	95 followed by a merging passes for these runs, which merging is often
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	96 very cleverly organised[1]. It is very important that the initial
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	97 sort produces the longest runs possible. Tournaments are a good way
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	98 to that. If, using all the memory available to hold a tournament, you
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	99 replace and percolate items that happen to fit the current run, you'll
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	100 produce runs which are twice the size of the memory for random input,
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	101 and much better for input fuzzily ordered.
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	102
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	103 Moreover, if you output the 0'th item on disk and get an input which
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	104 may not fit in the current tournament (because the value "wins" over
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	105 the last output value), it cannot fit in the heap, so the size of the
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	106 heap decreases. The freed memory could be cleverly reused immediately
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	107 for progressively building a second heap, which grows at exactly the
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	108 same rate the first heap is melting. When the first heap completely
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	109 vanishes, you switch heaps and start a new run. Clever and quite
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	110 effective!
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	111
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	112 In a word, heaps are useful memory structures to know. I use them in
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	113 a few applications, and I think it is good to keep a `heap' module
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	114 around. :-)
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	115
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	116 --------------------
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	117 [1] The disk balancing algorithms which are current, nowadays, are
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	118 more annoying than clever, and this is a consequence of the seeking
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	119 capabilities of the disks. On devices which cannot seek, like big
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	120 tape drives, the story was quite different, and one had to be very
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	121 clever to ensure (far in advance) that each tape movement will be the
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	122 most effective possible (that is, will best participate at
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	123 "progressing" the merge). Some tapes were even able to read
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	124 backwards, and this was also used to avoid the rewinding time.
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	125 Believe me, real good tape sorts were quite spectacular to watch!
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	126 From all times, sorting has always been a Great Art! :-)
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	127 """
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	128
40866 36d7b3b6ee59 Add merge() function to heapq. Raymond Hettinger <python@rcn.com> parents: 40541 diff changeset	129 __all__ = ['heappush', 'heappop', 'heapify', 'heapreplace', 'merge',
45747 cbb9e2f4b202 Issue 2274: Add heapq.heappushpop(). Raymond Hettinger <python@rcn.com> parents: 40988 diff changeset	130 'nlargest', 'nsmallest', 'heappushpop']
32316 9e5af45cefcb SF patch #969791: Add nlargest() and nsmallest() to heapq. Raymond Hettinger <python@rcn.com> parents: 31931 diff changeset	131
50748 87adcce48def Optimize heapq.nsmallest/nlargest for cases where n==1 or n>=size. Raymond Hettinger <python@rcn.com> parents: 50392 diff changeset	132 from itertools import islice, repeat, count, imap, izip, tee, chain
51773 326f6facc1aa Speedup and simplify negative counter using count's new step argument. Raymond Hettinger <python@rcn.com> parents: 51211 diff changeset	133 from operator import itemgetter
32332 f0eb7778a183 Improve the memory performance and speed of heapq.nsmallest() by using Raymond Hettinger <python@rcn.com> parents: 32316 diff changeset	134 import bisect
31931 63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	135
69327 103a2eb61069 Issue 3051: make pure python code pass the same tests as the C version. Raymond Hettinger <python@rcn.com> parents: 68256 diff changeset	136 def cmp_lt(x, y):
103a2eb61069 Issue 3051: make pure python code pass the same tests as the C version. Raymond Hettinger <python@rcn.com> parents: 68256 diff changeset	137 # Use __lt__ if available; otherwise, try __le__.
103a2eb61069 Issue 3051: make pure python code pass the same tests as the C version. Raymond Hettinger <python@rcn.com> parents: 68256 diff changeset	138 # In Py3.x, only __lt__ will be called.
103a2eb61069 Issue 3051: make pure python code pass the same tests as the C version. Raymond Hettinger <python@rcn.com> parents: 68256 diff changeset	139 return (x < y) if hasattr(x, '__lt__') else (not y <= x)
103a2eb61069 Issue 3051: make pure python code pass the same tests as the C version. Raymond Hettinger <python@rcn.com> parents: 68256 diff changeset	140
31931 63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	141 def heappush(heap, item):
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	142 """Push item onto heap, maintaining the heap invariant."""
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	143 heap.append(item)
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	144 _siftdown(heap, 0, len(heap)-1)
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	145
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	146 def heappop(heap):
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	147 """Pop the smallest item off the heap, maintaining the heap invariant."""
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	148 lastelt = heap.pop() # raises appropriate IndexError if heap is empty
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	149 if heap:
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	150 returnitem = heap[0]
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	151 heap[0] = lastelt
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	152 _siftup(heap, 0)
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	153 else:
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	154 returnitem = lastelt
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	155 return returnitem
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	156
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	157 def heapreplace(heap, item):
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	158 """Pop and return the current smallest value, and add the new item.
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	159
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	160 This is more efficient than heappop() followed by heappush(), and can be
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	161 more appropriate when using a fixed-size heap. Note that the value
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	162 returned may be larger than item! That constrains reasonable uses of
33415 dc97f581f233 Fix erroneous docstring comment. Raymond Hettinger <python@rcn.com> parents: 32390 diff changeset	163 this routine unless written as part of a conditional replacement:
32390 4c71bcfacde2 Improve the documented advice on how to best use heapq.heapreplace(). Raymond Hettinger <python@rcn.com> parents: 32336 diff changeset	164
33415 dc97f581f233 Fix erroneous docstring comment. Raymond Hettinger <python@rcn.com> parents: 32390 diff changeset	165 if item > heap[0]:
dc97f581f233 Fix erroneous docstring comment. Raymond Hettinger <python@rcn.com> parents: 32390 diff changeset	166 item = heapreplace(heap, item)
31931 63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	167 """
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	168 returnitem = heap[0] # raises appropriate IndexError if heap is empty
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	169 heap[0] = item
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	170 _siftup(heap, 0)
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	171 return returnitem
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	172
45747 cbb9e2f4b202 Issue 2274: Add heapq.heappushpop(). Raymond Hettinger <python@rcn.com> parents: 40988 diff changeset	173 def heappushpop(heap, item):
cbb9e2f4b202 Issue 2274: Add heapq.heappushpop(). Raymond Hettinger <python@rcn.com> parents: 40988 diff changeset	174 """Fast version of a heappush followed by a heappop."""
69327 103a2eb61069 Issue 3051: make pure python code pass the same tests as the C version. Raymond Hettinger <python@rcn.com> parents: 68256 diff changeset	175 if heap and cmp_lt(heap[0], item):
45747 cbb9e2f4b202 Issue 2274: Add heapq.heappushpop(). Raymond Hettinger <python@rcn.com> parents: 40988 diff changeset	176 item, heap[0] = heap[0], item
cbb9e2f4b202 Issue 2274: Add heapq.heappushpop(). Raymond Hettinger <python@rcn.com> parents: 40988 diff changeset	177 _siftup(heap, 0)
cbb9e2f4b202 Issue 2274: Add heapq.heappushpop(). Raymond Hettinger <python@rcn.com> parents: 40988 diff changeset	178 return item
cbb9e2f4b202 Issue 2274: Add heapq.heappushpop(). Raymond Hettinger <python@rcn.com> parents: 40988 diff changeset	179
31931 63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	180 def heapify(x):
69766 6e4f446835da Minor tweaks to a few comments in heapq Éric Araujo <merwok@netwok.org> parents: 69327 diff changeset	181 """Transform list into a heap, in-place, in O(len(x)) time."""
31931 63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	182 n = len(x)
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	183 # Transform bottom-up. The largest index there's any point to looking at
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	184 # is the largest with a child index in-range, so must have 2*i + 1 < n,
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	185 # or i < (n-1)/2. If n is even = 2j, this is (2j-1)/2 = j-1/2 so
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	186 # j-1 is the largest, which is n//2 - 1. If n is odd = 2*j+1, this is
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	187 # (2*j+1-1)/2 = j so j-1 is the largest, and that's again n//2-1.
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	188 for i in reversed(xrange(n//2)):
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	189 _siftup(x, i)
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	190
34037 d33b3a2b094c Fix argument order in pure python version of nsmallest() and nlargest(). Raymond Hettinger <python@rcn.com> parents: 33415 diff changeset	191 def nlargest(n, iterable):
32316 9e5af45cefcb SF patch #969791: Add nlargest() and nsmallest() to heapq. Raymond Hettinger <python@rcn.com> parents: 31931 diff changeset	192 """Find the n largest elements in a dataset.
9e5af45cefcb SF patch #969791: Add nlargest() and nsmallest() to heapq. Raymond Hettinger <python@rcn.com> parents: 31931 diff changeset	193
9e5af45cefcb SF patch #969791: Add nlargest() and nsmallest() to heapq. Raymond Hettinger <python@rcn.com> parents: 31931 diff changeset	194 Equivalent to: sorted(iterable, reverse=True)[:n]
9e5af45cefcb SF patch #969791: Add nlargest() and nsmallest() to heapq. Raymond Hettinger <python@rcn.com> parents: 31931 diff changeset	195 """
73221 57f73b0f921c Issue 13274: Make the pure python code for heapq more closely match the C implementation for an undefined corner case. Raymond Hettinger <python@rcn.com> parents: 69766 diff changeset	196 if n < 0:
57f73b0f921c Issue 13274: Make the pure python code for heapq more closely match the C implementation for an undefined corner case. Raymond Hettinger <python@rcn.com> parents: 69766 diff changeset	197 return []
32316 9e5af45cefcb SF patch #969791: Add nlargest() and nsmallest() to heapq. Raymond Hettinger <python@rcn.com> parents: 31931 diff changeset	198 it = iter(iterable)
9e5af45cefcb SF patch #969791: Add nlargest() and nsmallest() to heapq. Raymond Hettinger <python@rcn.com> parents: 31931 diff changeset	199 result = list(islice(it, n))
9e5af45cefcb SF patch #969791: Add nlargest() and nsmallest() to heapq. Raymond Hettinger <python@rcn.com> parents: 31931 diff changeset	200 if not result:
9e5af45cefcb SF patch #969791: Add nlargest() and nsmallest() to heapq. Raymond Hettinger <python@rcn.com> parents: 31931 diff changeset	201 return result
9e5af45cefcb SF patch #969791: Add nlargest() and nsmallest() to heapq. Raymond Hettinger <python@rcn.com> parents: 31931 diff changeset	202 heapify(result)
45748 db5b321edcbb Simplify the nlargest() code using heappushpop(). Raymond Hettinger <python@rcn.com> parents: 45747 diff changeset	203 _heappushpop = heappushpop
32316 9e5af45cefcb SF patch #969791: Add nlargest() and nsmallest() to heapq. Raymond Hettinger <python@rcn.com> parents: 31931 diff changeset	204 for elem in it:
55513 2c7e076b4ca9 Fix typo (already fixed in 2.7). Raymond Hettinger <python@rcn.com> parents: 50392 diff changeset	205 _heappushpop(result, elem)
32316 9e5af45cefcb SF patch #969791: Add nlargest() and nsmallest() to heapq. Raymond Hettinger <python@rcn.com> parents: 31931 diff changeset	206 result.sort(reverse=True)
9e5af45cefcb SF patch #969791: Add nlargest() and nsmallest() to heapq. Raymond Hettinger <python@rcn.com> parents: 31931 diff changeset	207 return result
9e5af45cefcb SF patch #969791: Add nlargest() and nsmallest() to heapq. Raymond Hettinger <python@rcn.com> parents: 31931 diff changeset	208
34037 d33b3a2b094c Fix argument order in pure python version of nsmallest() and nlargest(). Raymond Hettinger <python@rcn.com> parents: 33415 diff changeset	209 def nsmallest(n, iterable):
32316 9e5af45cefcb SF patch #969791: Add nlargest() and nsmallest() to heapq. Raymond Hettinger <python@rcn.com> parents: 31931 diff changeset	210 """Find the n smallest elements in a dataset.
9e5af45cefcb SF patch #969791: Add nlargest() and nsmallest() to heapq. Raymond Hettinger <python@rcn.com> parents: 31931 diff changeset	211
9e5af45cefcb SF patch #969791: Add nlargest() and nsmallest() to heapq. Raymond Hettinger <python@rcn.com> parents: 31931 diff changeset	212 Equivalent to: sorted(iterable)[:n]
9e5af45cefcb SF patch #969791: Add nlargest() and nsmallest() to heapq. Raymond Hettinger <python@rcn.com> parents: 31931 diff changeset	213 """
73221 57f73b0f921c Issue 13274: Make the pure python code for heapq more closely match the C implementation for an undefined corner case. Raymond Hettinger <python@rcn.com> parents: 69766 diff changeset	214 if n < 0:
57f73b0f921c Issue 13274: Make the pure python code for heapq more closely match the C implementation for an undefined corner case. Raymond Hettinger <python@rcn.com> parents: 69766 diff changeset	215 return []
32332 f0eb7778a183 Improve the memory performance and speed of heapq.nsmallest() by using Raymond Hettinger <python@rcn.com> parents: 32316 diff changeset	216 if hasattr(iterable, '__len__') and n * 10 <= len(iterable):
f0eb7778a183 Improve the memory performance and speed of heapq.nsmallest() by using Raymond Hettinger <python@rcn.com> parents: 32316 diff changeset	217 # For smaller values of n, the bisect method is faster than a minheap.
f0eb7778a183 Improve the memory performance and speed of heapq.nsmallest() by using Raymond Hettinger <python@rcn.com> parents: 32316 diff changeset	218 # It is also memory efficient, consuming only n elements of space.
f0eb7778a183 Improve the memory performance and speed of heapq.nsmallest() by using Raymond Hettinger <python@rcn.com> parents: 32316 diff changeset	219 it = iter(iterable)
f0eb7778a183 Improve the memory performance and speed of heapq.nsmallest() by using Raymond Hettinger <python@rcn.com> parents: 32316 diff changeset	220 result = sorted(islice(it, 0, n))
f0eb7778a183 Improve the memory performance and speed of heapq.nsmallest() by using Raymond Hettinger <python@rcn.com> parents: 32316 diff changeset	221 if not result:
f0eb7778a183 Improve the memory performance and speed of heapq.nsmallest() by using Raymond Hettinger <python@rcn.com> parents: 32316 diff changeset	222 return result
f0eb7778a183 Improve the memory performance and speed of heapq.nsmallest() by using Raymond Hettinger <python@rcn.com> parents: 32316 diff changeset	223 insort = bisect.insort
f0eb7778a183 Improve the memory performance and speed of heapq.nsmallest() by using Raymond Hettinger <python@rcn.com> parents: 32316 diff changeset	224 pop = result.pop
f0eb7778a183 Improve the memory performance and speed of heapq.nsmallest() by using Raymond Hettinger <python@rcn.com> parents: 32316 diff changeset	225 los = result[-1] # los --> Largest of the nsmallest
f0eb7778a183 Improve the memory performance and speed of heapq.nsmallest() by using Raymond Hettinger <python@rcn.com> parents: 32316 diff changeset	226 for elem in it:
69327 103a2eb61069 Issue 3051: make pure python code pass the same tests as the C version. Raymond Hettinger <python@rcn.com> parents: 68256 diff changeset	227 if cmp_lt(elem, los):
103a2eb61069 Issue 3051: make pure python code pass the same tests as the C version. Raymond Hettinger <python@rcn.com> parents: 68256 diff changeset	228 insort(result, elem)
103a2eb61069 Issue 3051: make pure python code pass the same tests as the C version. Raymond Hettinger <python@rcn.com> parents: 68256 diff changeset	229 pop()
103a2eb61069 Issue 3051: make pure python code pass the same tests as the C version. Raymond Hettinger <python@rcn.com> parents: 68256 diff changeset	230 los = result[-1]
32332 f0eb7778a183 Improve the memory performance and speed of heapq.nsmallest() by using Raymond Hettinger <python@rcn.com> parents: 32316 diff changeset	231 return result
f0eb7778a183 Improve the memory performance and speed of heapq.nsmallest() by using Raymond Hettinger <python@rcn.com> parents: 32316 diff changeset	232 # An alternative approach manifests the whole iterable in memory but
f0eb7778a183 Improve the memory performance and speed of heapq.nsmallest() by using Raymond Hettinger <python@rcn.com> parents: 32316 diff changeset	233 # saves comparisons by heapifying all at once. Also, saves time
f0eb7778a183 Improve the memory performance and speed of heapq.nsmallest() by using Raymond Hettinger <python@rcn.com> parents: 32316 diff changeset	234 # over bisect.insort() which has O(n) data movement time for every
f0eb7778a183 Improve the memory performance and speed of heapq.nsmallest() by using Raymond Hettinger <python@rcn.com> parents: 32316 diff changeset	235 # insertion. Finding the n smallest of an m length iterable requires
f0eb7778a183 Improve the memory performance and speed of heapq.nsmallest() by using Raymond Hettinger <python@rcn.com> parents: 32316 diff changeset	236 # O(m) + O(n log m) comparisons.
32316 9e5af45cefcb SF patch #969791: Add nlargest() and nsmallest() to heapq. Raymond Hettinger <python@rcn.com> parents: 31931 diff changeset	237 h = list(iterable)
9e5af45cefcb SF patch #969791: Add nlargest() and nsmallest() to heapq. Raymond Hettinger <python@rcn.com> parents: 31931 diff changeset	238 heapify(h)
9e5af45cefcb SF patch #969791: Add nlargest() and nsmallest() to heapq. Raymond Hettinger <python@rcn.com> parents: 31931 diff changeset	239 return map(heappop, repeat(h, min(n, len(h))))
9e5af45cefcb SF patch #969791: Add nlargest() and nsmallest() to heapq. Raymond Hettinger <python@rcn.com> parents: 31931 diff changeset	240
31931 63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	241 # 'heap' is a heap at all indices >= startpos, except possibly for pos. pos
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	242 # is the index of a leaf with a possibly out-of-order value. Restore the
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	243 # heap invariant.
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	244 def _siftdown(heap, startpos, pos):
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	245 newitem = heap[pos]
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	246 # Follow the path to the root, moving parents down until finding a place
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	247 # newitem fits.
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	248 while pos > startpos:
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	249 parentpos = (pos - 1) >> 1
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	250 parent = heap[parentpos]
69327 103a2eb61069 Issue 3051: make pure python code pass the same tests as the C version. Raymond Hettinger <python@rcn.com> parents: 68256 diff changeset	251 if cmp_lt(newitem, parent):
47402 2e8769d5a786 Implement heapq in terms of less-than (to match list.sort()). Raymond Hettinger <python@rcn.com> parents: 45748 diff changeset	252 heap[pos] = parent
2e8769d5a786 Implement heapq in terms of less-than (to match list.sort()). Raymond Hettinger <python@rcn.com> parents: 45748 diff changeset	253 pos = parentpos
2e8769d5a786 Implement heapq in terms of less-than (to match list.sort()). Raymond Hettinger <python@rcn.com> parents: 45748 diff changeset	254 continue
2e8769d5a786 Implement heapq in terms of less-than (to match list.sort()). Raymond Hettinger <python@rcn.com> parents: 45748 diff changeset	255 break
31931 63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	256 heap[pos] = newitem
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	257
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	258 # The child indices of heap index pos are already heaps, and we want to make
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	259 # a heap at index pos too. We do this by bubbling the smaller child of
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	260 # pos up (and so on with that child's children, etc) until hitting a leaf,
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	261 # then using _siftdown to move the oddball originally at index pos into place.
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	262 #
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	263 # We could break out of the loop as soon as we find a pos where newitem <=
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	264 # both its children, but turns out that's not a good idea, and despite that
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	265 # many books write the algorithm that way. During a heap pop, the last array
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	266 # element is sifted in, and that tends to be large, so that comparing it
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	267 # against values starting from the root usually doesn't pay (= usually doesn't
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	268 # get us out of the loop early). See Knuth, Volume 3, where this is
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	269 # explained and quantified in an exercise.
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	270 #
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	271 # Cutting the # of comparisons is important, since these routines have no
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	272 # way to extract "the priority" from an array element, so that intelligence
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	273 # is likely to be hiding in custom __cmp__ methods, or in array elements
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	274 # storing (priority, record) tuples. Comparisons are thus potentially
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	275 # expensive.
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	276 #
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	277 # On random arrays of length 1000, making this change cut the number of
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	278 # comparisons made by heapify() a little, and those made by exhaustive
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	279 # heappop() a lot, in accord with theory. Here are typical results from 3
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	280 # runs (3 just to demonstrate how small the variance is):
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	281 #
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	282 # Compares needed by heapify Compares needed by 1000 heappops
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	283 # -------------------------- --------------------------------
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	284 # 1837 cut to 1663 14996 cut to 8680
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	285 # 1855 cut to 1659 14966 cut to 8678
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	286 # 1847 cut to 1660 15024 cut to 8703
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	287 #
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	288 # Building the heap by using heappush() 1000 times instead required
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	289 # 2198, 2148, and 2219 compares: heapify() is more efficient, when
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	290 # you can use it.
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	291 #
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	292 # The total compares needed by list.sort() on the same lists were 8627,
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	293 # 8627, and 8632 (this should be compared to the sum of heapify() and
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	294 # heappop() compares): list.sort() is (unsurprisingly!) more efficient
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	295 # for sorting.
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	296
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	297 def _siftup(heap, pos):
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	298 endpos = len(heap)
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	299 startpos = pos
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	300 newitem = heap[pos]
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	301 # Bubble up the smaller child until hitting a leaf.
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	302 childpos = 2*pos + 1 # leftmost child position
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	303 while childpos < endpos:
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	304 # Set childpos to index of smaller child.
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	305 rightpos = childpos + 1
69327 103a2eb61069 Issue 3051: make pure python code pass the same tests as the C version. Raymond Hettinger <python@rcn.com> parents: 68256 diff changeset	306 if rightpos < endpos and not cmp_lt(heap[childpos], heap[rightpos]):
31931 63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	307 childpos = rightpos
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	308 # Move the smaller child up.
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	309 heap[pos] = heap[childpos]
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	310 pos = childpos
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	311 childpos = 2*pos + 1
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	312 # The leaf at pos is empty now. Put newitem there, and bubble it up
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	313 # to its final resting place (by sifting its parents down).
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	314 heap[pos] = newitem
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	315 _siftdown(heap, startpos, pos)
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	316
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	317 # If available, use C implementation
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	318 try:
52417 0507aab5fb11 Make life easier for non-CPython implementations. Raymond Hettinger <python@rcn.com> parents: 51773 diff changeset	319 from _heapq import *
31931 63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	320 except ImportError:
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	321 pass
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	322
40866 36d7b3b6ee59 Add merge() function to heapq. Raymond Hettinger <python@rcn.com> parents: 40541 diff changeset	323 def merge(*iterables):
36d7b3b6ee59 Add merge() function to heapq. Raymond Hettinger <python@rcn.com> parents: 40541 diff changeset	324 '''Merge multiple sorted inputs into a single sorted output.
36d7b3b6ee59 Add merge() function to heapq. Raymond Hettinger <python@rcn.com> parents: 40541 diff changeset	325
40988 a8c79b1e696a Docstring nit. Raymond Hettinger <python@rcn.com> parents: 40873 diff changeset	326 Similar to sorted(itertools.chain(*iterables)) but returns a generator,
40873 672b90757647 Fixup docstrings for merge(). Raymond Hettinger <python@rcn.com> parents: 40868 diff changeset	327 does not pull the data into memory all at once, and assumes that each of
672b90757647 Fixup docstrings for merge(). Raymond Hettinger <python@rcn.com> parents: 40868 diff changeset	328 the input streams is already sorted (smallest to largest).
40866 36d7b3b6ee59 Add merge() function to heapq. Raymond Hettinger <python@rcn.com> parents: 40541 diff changeset	329
36d7b3b6ee59 Add merge() function to heapq. Raymond Hettinger <python@rcn.com> parents: 40541 diff changeset	330 >>> list(merge([1,3,5,7], [0,2,4,8], [5,10,15,20], [], [25]))
36d7b3b6ee59 Add merge() function to heapq. Raymond Hettinger <python@rcn.com> parents: 40541 diff changeset	331 [0, 1, 2, 3, 4, 5, 5, 7, 8, 10, 15, 20, 25]
36d7b3b6ee59 Add merge() function to heapq. Raymond Hettinger <python@rcn.com> parents: 40541 diff changeset	332
36d7b3b6ee59 Add merge() function to heapq. Raymond Hettinger <python@rcn.com> parents: 40541 diff changeset	333 '''
40868 df0204ca9739 Use C heapreplace() instead of slower _siftup() in pure python. Raymond Hettinger <python@rcn.com> parents: 40867 diff changeset	334 _heappop, _heapreplace, _StopIteration = heappop, heapreplace, StopIteration
40866 36d7b3b6ee59 Add merge() function to heapq. Raymond Hettinger <python@rcn.com> parents: 40541 diff changeset	335
36d7b3b6ee59 Add merge() function to heapq. Raymond Hettinger <python@rcn.com> parents: 40541 diff changeset	336 h = []
36d7b3b6ee59 Add merge() function to heapq. Raymond Hettinger <python@rcn.com> parents: 40541 diff changeset	337 h_append = h.append
40867 d386b460993b Add tie-breaker count to preserve sort stability. Raymond Hettinger <python@rcn.com> parents: 40866 diff changeset	338 for itnum, it in enumerate(map(iter, iterables)):
40866 36d7b3b6ee59 Add merge() function to heapq. Raymond Hettinger <python@rcn.com> parents: 40541 diff changeset	339 try:
36d7b3b6ee59 Add merge() function to heapq. Raymond Hettinger <python@rcn.com> parents: 40541 diff changeset	340 next = it.next
40867 d386b460993b Add tie-breaker count to preserve sort stability. Raymond Hettinger <python@rcn.com> parents: 40866 diff changeset	341 h_append([next(), itnum, next])
40866 36d7b3b6ee59 Add merge() function to heapq. Raymond Hettinger <python@rcn.com> parents: 40541 diff changeset	342 except _StopIteration:
36d7b3b6ee59 Add merge() function to heapq. Raymond Hettinger <python@rcn.com> parents: 40541 diff changeset	343 pass
36d7b3b6ee59 Add merge() function to heapq. Raymond Hettinger <python@rcn.com> parents: 40541 diff changeset	344 heapify(h)
36d7b3b6ee59 Add merge() function to heapq. Raymond Hettinger <python@rcn.com> parents: 40541 diff changeset	345
36d7b3b6ee59 Add merge() function to heapq. Raymond Hettinger <python@rcn.com> parents: 40541 diff changeset	346 while 1:
36d7b3b6ee59 Add merge() function to heapq. Raymond Hettinger <python@rcn.com> parents: 40541 diff changeset	347 try:
36d7b3b6ee59 Add merge() function to heapq. Raymond Hettinger <python@rcn.com> parents: 40541 diff changeset	348 while 1:
40867 d386b460993b Add tie-breaker count to preserve sort stability. Raymond Hettinger <python@rcn.com> parents: 40866 diff changeset	349 v, itnum, next = s = h[0] # raises IndexError when h is empty
40866 36d7b3b6ee59 Add merge() function to heapq. Raymond Hettinger <python@rcn.com> parents: 40541 diff changeset	350 yield v
40867 d386b460993b Add tie-breaker count to preserve sort stability. Raymond Hettinger <python@rcn.com> parents: 40866 diff changeset	351 s[0] = next() # raises StopIteration when exhausted
40868 df0204ca9739 Use C heapreplace() instead of slower _siftup() in pure python. Raymond Hettinger <python@rcn.com> parents: 40867 diff changeset	352 _heapreplace(h, s) # restore heap condition
40866 36d7b3b6ee59 Add merge() function to heapq. Raymond Hettinger <python@rcn.com> parents: 40541 diff changeset	353 except _StopIteration:
40867 d386b460993b Add tie-breaker count to preserve sort stability. Raymond Hettinger <python@rcn.com> parents: 40866 diff changeset	354 _heappop(h) # remove empty iterator
40866 36d7b3b6ee59 Add merge() function to heapq. Raymond Hettinger <python@rcn.com> parents: 40541 diff changeset	355 except IndexError:
36d7b3b6ee59 Add merge() function to heapq. Raymond Hettinger <python@rcn.com> parents: 40541 diff changeset	356 return
36d7b3b6ee59 Add merge() function to heapq. Raymond Hettinger <python@rcn.com> parents: 40541 diff changeset	357
34079 c4b13fa18a10 Add key= argument to heapq.nsmallest() and heapq.nlargest(). Raymond Hettinger <python@rcn.com> parents: 34037 diff changeset	358 # Extend the implementations of nsmallest and nlargest to use a key= argument
c4b13fa18a10 Add key= argument to heapq.nsmallest() and heapq.nlargest(). Raymond Hettinger <python@rcn.com> parents: 34037 diff changeset	359 _nsmallest = nsmallest
c4b13fa18a10 Add key= argument to heapq.nsmallest() and heapq.nlargest(). Raymond Hettinger <python@rcn.com> parents: 34037 diff changeset	360 def nsmallest(n, iterable, key=None):
c4b13fa18a10 Add key= argument to heapq.nsmallest() and heapq.nlargest(). Raymond Hettinger <python@rcn.com> parents: 34037 diff changeset	361 """Find the n smallest elements in a dataset.
c4b13fa18a10 Add key= argument to heapq.nsmallest() and heapq.nlargest(). Raymond Hettinger <python@rcn.com> parents: 34037 diff changeset	362
c4b13fa18a10 Add key= argument to heapq.nsmallest() and heapq.nlargest(). Raymond Hettinger <python@rcn.com> parents: 34037 diff changeset	363 Equivalent to: sorted(iterable, key=key)[:n]
c4b13fa18a10 Add key= argument to heapq.nsmallest() and heapq.nlargest(). Raymond Hettinger <python@rcn.com> parents: 34037 diff changeset	364 """
50748 87adcce48def Optimize heapq.nsmallest/nlargest for cases where n==1 or n>=size. Raymond Hettinger <python@rcn.com> parents: 50392 diff changeset	365 # Short-cut for n==1 is to use min() when len(iterable)>0
87adcce48def Optimize heapq.nsmallest/nlargest for cases where n==1 or n>=size. Raymond Hettinger <python@rcn.com> parents: 50392 diff changeset	366 if n == 1:
87adcce48def Optimize heapq.nsmallest/nlargest for cases where n==1 or n>=size. Raymond Hettinger <python@rcn.com> parents: 50392 diff changeset	367 it = iter(iterable)
87adcce48def Optimize heapq.nsmallest/nlargest for cases where n==1 or n>=size. Raymond Hettinger <python@rcn.com> parents: 50392 diff changeset	368 head = list(islice(it, 1))
87adcce48def Optimize heapq.nsmallest/nlargest for cases where n==1 or n>=size. Raymond Hettinger <python@rcn.com> parents: 50392 diff changeset	369 if not head:
87adcce48def Optimize heapq.nsmallest/nlargest for cases where n==1 or n>=size. Raymond Hettinger <python@rcn.com> parents: 50392 diff changeset	370 return []
87adcce48def Optimize heapq.nsmallest/nlargest for cases where n==1 or n>=size. Raymond Hettinger <python@rcn.com> parents: 50392 diff changeset	371 if key is None:
87adcce48def Optimize heapq.nsmallest/nlargest for cases where n==1 or n>=size. Raymond Hettinger <python@rcn.com> parents: 50392 diff changeset	372 return [min(chain(head, it))]
87adcce48def Optimize heapq.nsmallest/nlargest for cases where n==1 or n>=size. Raymond Hettinger <python@rcn.com> parents: 50392 diff changeset	373 return [min(chain(head, it), key=key)]
87adcce48def Optimize heapq.nsmallest/nlargest for cases where n==1 or n>=size. Raymond Hettinger <python@rcn.com> parents: 50392 diff changeset	374
69766 6e4f446835da Minor tweaks to a few comments in heapq Éric Araujo <merwok@netwok.org> parents: 69327 diff changeset	375 # When n>=size, it's faster to use sorted()
50748 87adcce48def Optimize heapq.nsmallest/nlargest for cases where n==1 or n>=size. Raymond Hettinger <python@rcn.com> parents: 50392 diff changeset	376 try:
87adcce48def Optimize heapq.nsmallest/nlargest for cases where n==1 or n>=size. Raymond Hettinger <python@rcn.com> parents: 50392 diff changeset	377 size = len(iterable)
87adcce48def Optimize heapq.nsmallest/nlargest for cases where n==1 or n>=size. Raymond Hettinger <python@rcn.com> parents: 50392 diff changeset	378 except (TypeError, AttributeError):
87adcce48def Optimize heapq.nsmallest/nlargest for cases where n==1 or n>=size. Raymond Hettinger <python@rcn.com> parents: 50392 diff changeset	379 pass
87adcce48def Optimize heapq.nsmallest/nlargest for cases where n==1 or n>=size. Raymond Hettinger <python@rcn.com> parents: 50392 diff changeset	380 else:
87adcce48def Optimize heapq.nsmallest/nlargest for cases where n==1 or n>=size. Raymond Hettinger <python@rcn.com> parents: 50392 diff changeset	381 if n >= size:
87adcce48def Optimize heapq.nsmallest/nlargest for cases where n==1 or n>=size. Raymond Hettinger <python@rcn.com> parents: 50392 diff changeset	382 return sorted(iterable, key=key)[:n]
87adcce48def Optimize heapq.nsmallest/nlargest for cases where n==1 or n>=size. Raymond Hettinger <python@rcn.com> parents: 50392 diff changeset	383
87adcce48def Optimize heapq.nsmallest/nlargest for cases where n==1 or n>=size. Raymond Hettinger <python@rcn.com> parents: 50392 diff changeset	384 # When key is none, use simpler decoration
50392 3853c15532c4 Issue 4790: Eliminate unnecessary work from heapq's nlargest() and nsmallest() Raymond Hettinger <python@rcn.com> parents: 47402 diff changeset	385 if key is None:
3853c15532c4 Issue 4790: Eliminate unnecessary work from heapq's nlargest() and nsmallest() Raymond Hettinger <python@rcn.com> parents: 47402 diff changeset	386 it = izip(iterable, count()) # decorate
3853c15532c4 Issue 4790: Eliminate unnecessary work from heapq's nlargest() and nsmallest() Raymond Hettinger <python@rcn.com> parents: 47402 diff changeset	387 result = _nsmallest(n, it)
3853c15532c4 Issue 4790: Eliminate unnecessary work from heapq's nlargest() and nsmallest() Raymond Hettinger <python@rcn.com> parents: 47402 diff changeset	388 return map(itemgetter(0), result) # undecorate
50748 87adcce48def Optimize heapq.nsmallest/nlargest for cases where n==1 or n>=size. Raymond Hettinger <python@rcn.com> parents: 50392 diff changeset	389
87adcce48def Optimize heapq.nsmallest/nlargest for cases where n==1 or n>=size. Raymond Hettinger <python@rcn.com> parents: 50392 diff changeset	390 # General case, slowest method
34079 c4b13fa18a10 Add key= argument to heapq.nsmallest() and heapq.nlargest(). Raymond Hettinger <python@rcn.com> parents: 34037 diff changeset	391 in1, in2 = tee(iterable)
c4b13fa18a10 Add key= argument to heapq.nsmallest() and heapq.nlargest(). Raymond Hettinger <python@rcn.com> parents: 34037 diff changeset	392 it = izip(imap(key, in1), count(), in2) # decorate
c4b13fa18a10 Add key= argument to heapq.nsmallest() and heapq.nlargest(). Raymond Hettinger <python@rcn.com> parents: 34037 diff changeset	393 result = _nsmallest(n, it)
c4b13fa18a10 Add key= argument to heapq.nsmallest() and heapq.nlargest(). Raymond Hettinger <python@rcn.com> parents: 34037 diff changeset	394 return map(itemgetter(2), result) # undecorate
c4b13fa18a10 Add key= argument to heapq.nsmallest() and heapq.nlargest(). Raymond Hettinger <python@rcn.com> parents: 34037 diff changeset	395
c4b13fa18a10 Add key= argument to heapq.nsmallest() and heapq.nlargest(). Raymond Hettinger <python@rcn.com> parents: 34037 diff changeset	396 _nlargest = nlargest
c4b13fa18a10 Add key= argument to heapq.nsmallest() and heapq.nlargest(). Raymond Hettinger <python@rcn.com> parents: 34037 diff changeset	397 def nlargest(n, iterable, key=None):
c4b13fa18a10 Add key= argument to heapq.nsmallest() and heapq.nlargest(). Raymond Hettinger <python@rcn.com> parents: 34037 diff changeset	398 """Find the n largest elements in a dataset.
c4b13fa18a10 Add key= argument to heapq.nsmallest() and heapq.nlargest(). Raymond Hettinger <python@rcn.com> parents: 34037 diff changeset	399
c4b13fa18a10 Add key= argument to heapq.nsmallest() and heapq.nlargest(). Raymond Hettinger <python@rcn.com> parents: 34037 diff changeset	400 Equivalent to: sorted(iterable, key=key, reverse=True)[:n]
c4b13fa18a10 Add key= argument to heapq.nsmallest() and heapq.nlargest(). Raymond Hettinger <python@rcn.com> parents: 34037 diff changeset	401 """
50748 87adcce48def Optimize heapq.nsmallest/nlargest for cases where n==1 or n>=size. Raymond Hettinger <python@rcn.com> parents: 50392 diff changeset	402
87adcce48def Optimize heapq.nsmallest/nlargest for cases where n==1 or n>=size. Raymond Hettinger <python@rcn.com> parents: 50392 diff changeset	403 # Short-cut for n==1 is to use max() when len(iterable)>0
87adcce48def Optimize heapq.nsmallest/nlargest for cases where n==1 or n>=size. Raymond Hettinger <python@rcn.com> parents: 50392 diff changeset	404 if n == 1:
87adcce48def Optimize heapq.nsmallest/nlargest for cases where n==1 or n>=size. Raymond Hettinger <python@rcn.com> parents: 50392 diff changeset	405 it = iter(iterable)
87adcce48def Optimize heapq.nsmallest/nlargest for cases where n==1 or n>=size. Raymond Hettinger <python@rcn.com> parents: 50392 diff changeset	406 head = list(islice(it, 1))
87adcce48def Optimize heapq.nsmallest/nlargest for cases where n==1 or n>=size. Raymond Hettinger <python@rcn.com> parents: 50392 diff changeset	407 if not head:
87adcce48def Optimize heapq.nsmallest/nlargest for cases where n==1 or n>=size. Raymond Hettinger <python@rcn.com> parents: 50392 diff changeset	408 return []
87adcce48def Optimize heapq.nsmallest/nlargest for cases where n==1 or n>=size. Raymond Hettinger <python@rcn.com> parents: 50392 diff changeset	409 if key is None:
87adcce48def Optimize heapq.nsmallest/nlargest for cases where n==1 or n>=size. Raymond Hettinger <python@rcn.com> parents: 50392 diff changeset	410 return [max(chain(head, it))]
87adcce48def Optimize heapq.nsmallest/nlargest for cases where n==1 or n>=size. Raymond Hettinger <python@rcn.com> parents: 50392 diff changeset	411 return [max(chain(head, it), key=key)]
87adcce48def Optimize heapq.nsmallest/nlargest for cases where n==1 or n>=size. Raymond Hettinger <python@rcn.com> parents: 50392 diff changeset	412
69766 6e4f446835da Minor tweaks to a few comments in heapq Éric Araujo <merwok@netwok.org> parents: 69327 diff changeset	413 # When n>=size, it's faster to use sorted()
50748 87adcce48def Optimize heapq.nsmallest/nlargest for cases where n==1 or n>=size. Raymond Hettinger <python@rcn.com> parents: 50392 diff changeset	414 try:
87adcce48def Optimize heapq.nsmallest/nlargest for cases where n==1 or n>=size. Raymond Hettinger <python@rcn.com> parents: 50392 diff changeset	415 size = len(iterable)
87adcce48def Optimize heapq.nsmallest/nlargest for cases where n==1 or n>=size. Raymond Hettinger <python@rcn.com> parents: 50392 diff changeset	416 except (TypeError, AttributeError):
87adcce48def Optimize heapq.nsmallest/nlargest for cases where n==1 or n>=size. Raymond Hettinger <python@rcn.com> parents: 50392 diff changeset	417 pass
87adcce48def Optimize heapq.nsmallest/nlargest for cases where n==1 or n>=size. Raymond Hettinger <python@rcn.com> parents: 50392 diff changeset	418 else:
87adcce48def Optimize heapq.nsmallest/nlargest for cases where n==1 or n>=size. Raymond Hettinger <python@rcn.com> parents: 50392 diff changeset	419 if n >= size:
87adcce48def Optimize heapq.nsmallest/nlargest for cases where n==1 or n>=size. Raymond Hettinger <python@rcn.com> parents: 50392 diff changeset	420 return sorted(iterable, key=key, reverse=True)[:n]
87adcce48def Optimize heapq.nsmallest/nlargest for cases where n==1 or n>=size. Raymond Hettinger <python@rcn.com> parents: 50392 diff changeset	421
87adcce48def Optimize heapq.nsmallest/nlargest for cases where n==1 or n>=size. Raymond Hettinger <python@rcn.com> parents: 50392 diff changeset	422 # When key is none, use simpler decoration
50392 3853c15532c4 Issue 4790: Eliminate unnecessary work from heapq's nlargest() and nsmallest() Raymond Hettinger <python@rcn.com> parents: 47402 diff changeset	423 if key is None:
51773 326f6facc1aa Speedup and simplify negative counter using count's new step argument. Raymond Hettinger <python@rcn.com> parents: 51211 diff changeset	424 it = izip(iterable, count(0,-1)) # decorate
50392 3853c15532c4 Issue 4790: Eliminate unnecessary work from heapq's nlargest() and nsmallest() Raymond Hettinger <python@rcn.com> parents: 47402 diff changeset	425 result = _nlargest(n, it)
3853c15532c4 Issue 4790: Eliminate unnecessary work from heapq's nlargest() and nsmallest() Raymond Hettinger <python@rcn.com> parents: 47402 diff changeset	426 return map(itemgetter(0), result) # undecorate
50748 87adcce48def Optimize heapq.nsmallest/nlargest for cases where n==1 or n>=size. Raymond Hettinger <python@rcn.com> parents: 50392 diff changeset	427
87adcce48def Optimize heapq.nsmallest/nlargest for cases where n==1 or n>=size. Raymond Hettinger <python@rcn.com> parents: 50392 diff changeset	428 # General case, slowest method
34079 c4b13fa18a10 Add key= argument to heapq.nsmallest() and heapq.nlargest(). Raymond Hettinger <python@rcn.com> parents: 34037 diff changeset	429 in1, in2 = tee(iterable)
51773 326f6facc1aa Speedup and simplify negative counter using count's new step argument. Raymond Hettinger <python@rcn.com> parents: 51211 diff changeset	430 it = izip(imap(key, in1), count(0,-1), in2) # decorate
34079 c4b13fa18a10 Add key= argument to heapq.nsmallest() and heapq.nlargest(). Raymond Hettinger <python@rcn.com> parents: 34037 diff changeset	431 result = _nlargest(n, it)
c4b13fa18a10 Add key= argument to heapq.nsmallest() and heapq.nlargest(). Raymond Hettinger <python@rcn.com> parents: 34037 diff changeset	432 return map(itemgetter(2), result) # undecorate
c4b13fa18a10 Add key= argument to heapq.nsmallest() and heapq.nlargest(). Raymond Hettinger <python@rcn.com> parents: 34037 diff changeset	433
31931 63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	434 if __name__ == "__main__":
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	435 # Simple sanity test
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	436 heap = []
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	437 data = [1, 3, 5, 7, 9, 2, 4, 6, 8, 0]
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	438 for item in data:
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	439 heappush(heap, item)
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	440 sort = []
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	441 while heap:
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	442 sort.append(heappop(heap))
63b68cb2b442 * Restore the pure python version of heapq.py. Raymond Hettinger <python@rcn.com> parents: diff changeset	443 print sort
40866 36d7b3b6ee59 Add merge() function to heapq. Raymond Hettinger <python@rcn.com> parents: 40541 diff changeset	444
36d7b3b6ee59 Add merge() function to heapq. Raymond Hettinger <python@rcn.com> parents: 40541 diff changeset	445 import doctest
36d7b3b6ee59 Add merge() function to heapq. Raymond Hettinger <python@rcn.com> parents: 40541 diff changeset	446 doctest.testmod()

Mercurial > cpython-lru_cache-weakref

annotate Lib/heapq.py @ 79675:c0a2294de787 2.7