tree 1cea4e21c0bb515702af1cd180ff350cfc1b9ebf
parent 6bdbc9e0b1d17e637236dc71b3fa775c23dd1d40
author Tim Peters <tim.peters@gmail.com> 1028368612 +0000
committer Tim Peters <tim.peters@gmail.com> 1028368612 +0000
HG:extra convert_revision:svn%3A6015fed2-1504-0410-9fe1-9d1591cc4771/python/branches/legacy-trunk%4027908

Large code rearrangement to use better algorithms, in the sense of needing
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.