summaryrefslogtreecommitdiffstats
path: root/Lib/heapq.py
Commit message (Collapse)AuthorAgeFilesLines
* Fix typo in comment.Fred Drake2002-11-131-2/+2
|
* Added __all__.Raymond Hettinger2002-10-301-0/+2
|
* Fixed misspelling in comment.Tim Peters2002-08-111-1/+1
|
* Whitespace normalization.Tim Peters2002-08-081-1/+1
|
* Simplify heapreplace() -- there's no need for an explicit test forGuido van Rossum2002-08-071-7/+4
| | | | empty heap, since heap[0] raises the appropriate IndexError already.
* _siftup(): __le__ is now the only comparison operator used on arrayTim Peters2002-08-031-1/+1
| | | | elements.
* Added new heapreplace(heap, item) function, to pop (and return) theTim Peters2002-08-031-0/+18
| | | | | currently-smallest value, and add item, in one gulp. See the second N-Best algorithm in the test suite for a natural use.
* Large code rearrangement to use better algorithms, in the sense of needingTim Peters2002-08-031-39/+79
| | | | | | | | | | | | substantially fewer array-element compares. This is best practice as of Kntuh Volume 3 Ed 2, and the code is actually simpler this way (although the key idea may be counter-intuitive at first glance! breaking out of a loop early loses when it costs more to try to get out early than getting out early saves). Also added a comment block explaining the difference and giving some real counts; demonstrating that heapify() is more efficient than repeated heappush(); and emphasizing the obvious point thatlist.sort() is more efficient if what you really want to do is sort.
* Minor fiddling, including a simple class to implement a heap iteratorTim Peters2002-08-031-5/+5
| | | | | in the test file. I have docs for heapq.heapify ready to check in, but Jack appears to have left behind a stale lock in the Doc/lib directory.
* Augment credits.Guido van Rossum2002-08-021-1/+1
|
* Hmm! I thought I checked this in before! Oh well.Tim Peters2002-08-021-9/+29
| | | | | | | | | | | | 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).
* Add a PEP-263-style encoding turd^H^H^H^Hdeclaration, because there'sGuido van Rossum2002-08-021-0/+2
| | | | a c-cedilla in one of the docstrings.
* heappop(): Added comments; simplified and sped the code.Tim Peters2002-08-021-21/+19
|
* heappop(): Use "while True" instead of "while 1".Tim Peters2002-08-021-1/+1
|
* Don't use true division where int division was intended. For that matter,Tim Peters2002-08-021-1/+1
| | | | don't use division at all.
* Add Kevin O'Connor, author of the heapq code.Guido van Rossum2002-08-021-0/+2
|
* Adding the heap queue algorithm, per discussion in python-dev lastGuido van Rossum2002-08-021-0/+176
week.
generated by cgit v0.12 at 2024-10-21 08:26:47 (GMT)