/
usr
/
share
/
doc
/
python2-docs
/
html
/
library
/
/usr/share/doc/python2-docs/html/library
mkdir
upload
Name
Size
Mode
Actions
2to3.html
59507
0644
edit
dl
rm
abc.html
25826
0644
edit
dl
rm
aepack.html
14164
0644
edit
dl
rm
aetools.html
16389
0644
edit
dl
rm
aetypes.html
21021
0644
edit
dl
rm
aifc.html
25064
0644
edit
dl
rm
al.html
18672
0644
edit
dl
rm
allos.html
35297
0644
edit
dl
rm
anydbm.html
18124
0644
edit
dl
rm
archiving.html
10078
0644
edit
dl
rm
argparse.html
263616
0644
edit
dl
rm
array.html
31855
0644
edit
dl
rm
ast.html
38167
0644
edit
dl
rm
asynchat.html
33930
0644
edit
dl
rm
asyncore.html
40631
0644
edit
dl
rm
atexit.html
18455
0644
edit
dl
rm
audioop.html
34252
0644
edit
dl
rm
autogil.html
8733
0644
edit
dl
rm
base64.html
21862
0644
edit
dl
rm
basehttpserver.html
37441
0644
edit
dl
rm
bastion.html
11798
0644
edit
dl
rm
bdb.html
41395
0644
edit
dl
rm
binascii.html
22997
0644
edit
dl
rm
binhex.html
11309
0644
edit
dl
rm
bisect.html
24666
0644
edit
dl
rm
bsddb.html
28589
0644
edit
dl
rm
bz2.html
29048
0644
edit
dl
rm
calendar.html
41762
0644
edit
dl
rm
carbon.html
51998
0644
edit
dl
rm
cd.html
30033
0644
edit
dl
rm
cgi.html
55922
0644
edit
dl
rm
cgihttpserver.html
14026
0644
edit
dl
rm
cgitb.html
12263
0644
edit
dl
rm
chunk.html
15899
0644
edit
dl
rm
cmath.html
28365
0644
edit
dl
rm
cmd.html
29042
0644
edit
dl
rm
code.html
26959
0644
edit
dl
rm
codecs.html
118258
0644
edit
dl
rm
codeop.html
15898
0644
edit
dl
rm
collections.html
147647
0644
edit
dl
rm
colorpicker.html
8035
0644
edit
dl
rm
colorsys.html
11919
0644
edit
dl
rm
commands.html
15516
0644
edit
dl
rm
compileall.html
18621
0644
edit
dl
rm
compiler.html
75897
0644
edit
dl
rm
configparser.html
67751
0644
edit
dl
rm
constants.html
13979
0644
edit
dl
rm
contextlib.html
22777
0644
edit
dl
rm
cookie.html
41854
0644
edit
dl
rm
cookielib.html
91032
0644
edit
dl
rm
copy.html
13004
0644
edit
dl
rm
copy_reg.html
14691
0644
edit
dl
rm
crypt.html
10647
0644
edit
dl
rm
crypto.html
7761
0644
edit
dl
rm
csv.html
76456
0644
edit
dl
rm
ctypes.html
264575
0644
edit
dl
rm
curses.ascii.html
24873
0644
edit
dl
rm
curses.html
167501
0644
edit
dl
rm
curses.panel.html
15824
0644
edit
dl
rm
custominterp.html
8026
0644
edit
dl
rm
datatypes.html
18015
0644
edit
dl
rm
datetime.html
253438
0644
edit
dl
rm
dbhash.html
16825
0644
edit
dl
rm
dbm.html
13507
0644
edit
dl
rm
debug.html
10703
0644
edit
dl
rm
decimal.html
222315
0644
edit
dl
rm
development.html
14828
0644
edit
dl
rm
difflib.html
91975
0644
edit
dl
rm
dircache.html
12299
0644
edit
dl
rm
dis.html
84156
0644
edit
dl
rm
distribution.html
7679
0644
edit
dl
rm
distutils.html
10152
0644
edit
dl
rm
dl.html
17668
0644
edit
dl
rm
doctest.html
185883
0644
edit
dl
rm
docxmlrpcserver.html
17573
0644
edit
dl
rm
dumbdbm.html
15549
0644
edit
dl
rm
dummy_thread.html
10065
0644
edit
dl
rm
dummy_threading.html
8934
0644
edit
dl
rm
easydialogs.html
33124
0644
edit
dl
rm
email-examples.html
47424
0644
edit
dl
rm
email.charset.html
29424
0644
edit
dl
rm
email.encoders.html
12847
0644
edit
dl
rm
email.errors.html
17952
0644
edit
dl
rm
email.generator.html
23141
0644
edit
dl
rm
email.header.html
29108
0644
edit
dl
rm
email.html
55722
0644
edit
dl
rm
email.iterators.html
12623
0644
edit
dl
rm
email.message.html
70189
0644
edit
dl
rm
email.mime.html
31655
0644
edit
dl
rm
email.parser.html
35142
0644
edit
dl
rm
email.utils.html
27076
0644
edit
dl
rm
ensurepip.html
18327
0644
edit
dl
rm
errno.html
40246
0644
edit
dl
rm
exceptions.html
63693
0644
edit
dl
rm
fcntl.html
26245
0644
edit
dl
rm
filecmp.html
23997
0644
edit
dl
rm
fileformats.html
9653
0644
edit
dl
rm
fileinput.html
27071
0644
edit
dl
rm
filesys.html
10866
0644
edit
dl
rm
fl.html
56525
0644
edit
dl
rm
fm.html
13009
0644
edit
dl
rm
fnmatch.html
16258
0644
edit
dl
rm
formatter.html
37371
0644
edit
dl
rm
fpectl.html
16879
0644
edit
dl
rm
fpformat.html
11455
0644
edit
dl
rm
fractions.html
24888
0644
edit
dl
rm
framework.html
36934
0644
edit
dl
rm
frameworks.html
7551
0644
edit
dl
rm
ftplib.html
49577
0644
edit
dl
rm
functions.html
205640
0644
edit
dl
rm
functools.html
29645
0644
edit
dl
rm
future_builtins.html
14477
0644
edit
dl
rm
gc.html
28423
0644
edit
dl
rm
gdbm.html
17805
0644
edit
dl
rm
gensuitemodule.html
12574
0644
edit
dl
rm
getopt.html
25280
0644
edit
dl
rm
getpass.html
11426
0644
edit
dl
rm
gettext.html
84971
0644
edit
dl
rm
gl.html
24342
0644
edit
dl
rm
glob.html
14430
0644
edit
dl
rm
grp.html
11316
0644
edit
dl
rm
gzip.html
20576
0644
edit
dl
rm
hashlib.html
25467
0644
edit
dl
rm
heapq.html
34890
0644
edit
dl
rm
hmac.html
14374
0644
edit
dl
rm
hotshot.html
20147
0644
edit
dl
rm
htmllib.html
27682
0644
edit
dl
rm
htmlparser.html
42433
0644
edit
dl
rm
httplib.html
70932
0644
edit
dl
rm
i18n.html
10047
0644
edit
dl
rm
ic.html
18654
0644
edit
dl
rm
idle.html
42148
0644
edit
dl
rm
imageop.html
16099
0644
edit
dl
rm
imaplib.html
58515
0644
edit
dl
rm
imgfile.html
12732
0644
edit
dl
rm
imghdr.html
12238
0644
edit
dl
rm
imp.html
37603
0644
edit
dl
rm
importlib.html
8926
0644
edit
dl
rm
imputil.html
33563
0644
edit
dl
rm
index.html
79088
0644
edit
dl
rm
inspect.html
56823
0644
edit
dl
rm
internet.html
26138
0644
edit
dl
rm
intro.html
9353
0644
edit
dl
rm
io.html
113701
0644
edit
dl
rm
ipc.html
16598
0644
edit
dl
rm
itertools.html
125397
0644
edit
dl
rm
jpeg.html
13757
0644
edit
dl
rm
json.html
73678
0644
edit
dl
rm
keyword.html
8210
0644
edit
dl
rm
language.html
11687
0644
edit
dl
rm
linecache.html
11416
0644
edit
dl
rm
locale.html
61576
0644
edit
dl
rm
logging.config.html
80045
0644
edit
dl
rm
logging.handlers.html
80194
0644
edit
dl
rm
logging.html
110254
0644
edit
dl
rm
mac.html
23376
0644
edit
dl
rm
macos.html
16129
0644
edit
dl
rm
macosa.html
14080
0644
edit
dl
rm
macostools.html
16898
0644
edit
dl
rm
macpath.html
8386
0644
edit
dl
rm
mailbox.html
171121
0644
edit
dl
rm
mailcap.html
14132
0644
edit
dl
rm
markup.html
19862
0644
edit
dl
rm
marshal.html
19456
0644
edit
dl
rm
math.html
44015
0644
edit
dl
rm
md5.html
15123
0644
edit
dl
rm
mhlib.html
24123
0644
edit
dl
rm
mimetools.html
21206
0644
edit
dl
rm
mimetypes.html
30634
0644
edit
dl
rm
mimewriter.html
16078
0644
edit
dl
rm
mimify.html
15279
0644
edit
dl
rm
miniaeframe.html
13109
0644
edit
dl
rm
misc.html
7236
0644
edit
dl
rm
mm.html
9570
0644
edit
dl
rm
mmap.html
30832
0644
edit
dl
rm
modulefinder.html
18096
0644
edit
dl
rm
modules.html
9017
0644
edit
dl
rm
msilib.html
57853
0644
edit
dl
rm
msvcrt.html
21232
0644
edit
dl
rm
multifile.html
26256
0644
edit
dl
rm
multiprocessing.html
414535
0644
edit
dl
rm
mutex.html
12147
0644
edit
dl
rm
netdata.html
18379
0644
edit
dl
rm
netrc.html
14021
0644
edit
dl
rm
new.html
13177
0644
edit
dl
rm
nis.html
11502
0644
edit
dl
rm
nntplib.html
45689
0644
edit
dl
rm
numbers.html
40636
0644
edit
dl
rm
numeric.html
14292
0644
edit
dl
rm
operator.html
93622
0644
edit
dl
rm
optparse.html
250109
0644
edit
dl
rm
os.html
240195
0644
edit
dl
rm
os.path.html
43402
0644
edit
dl
rm
ossaudiodev.html
45594
0644
edit
dl
rm
othergui.html
9403
0644
edit
dl
rm
parser.html
42558
0644
edit
dl
rm
pdb.html
38603
0644
edit
dl
rm
persistence.html
15676
0644
edit
dl
rm
pickle.html
109684
0644
edit
dl
rm
pickletools.html
11475
0644
edit
dl
rm
pipes.html
19685
0644
edit
dl
rm
pkgutil.html
27367
0644
edit
dl
rm
platform.html
31599
0644
edit
dl
rm
plistlib.html
18344
0644
edit
dl
rm
popen2.html
27601
0644
edit
dl
rm
poplib.html
24320
0644
edit
dl
rm
posix.html
16626
0644
edit
dl
rm
posixfile.html
21387
0644
edit
dl
rm
pprint.html
32207
0644
edit
dl
rm
profile.html
72788
0644
edit
dl
rm
pty.html
10195
0644
edit
dl
rm
pwd.html
12388
0644
edit
dl
rm
pyclbr.html
15812
0644
edit
dl
rm
pydoc.html
13650
0644
edit
dl
rm
pyexpat.html
80886
0644
edit
dl
rm
python.html
12854
0644
edit
dl
rm
py_compile.html
11932
0644
edit
dl
rm
queue.html
26856
0644
edit
dl
rm
quopri.html
12739
0644
edit
dl
rm
random.html
42722
0644
edit
dl
rm
re.html
155985
0644
edit
dl
rm
readline.html
37383
0644
edit
dl
rm
repr.html
21778
0644
edit
dl
rm
resource.html
28286
0644
edit
dl
rm
restricted.html
12366
0644
edit
dl
rm
rexec.html
40566
0644
edit
dl
rm
rfc822.html
46408
0644
edit
dl
rm
rlcompleter.html
14460
0644
edit
dl
rm
robotparser.html
13403
0644
edit
dl
rm
runpy.html
21925
0644
edit
dl
rm
sched.html
19878
0644
edit
dl
rm
scrolledtext.html
9728
0644
edit
dl
rm
select.html
44090
0644
edit
dl
rm
sets.html
40151
0644
edit
dl
rm
sgi.html
10371
0644
edit
dl
rm
sgmllib.html
34464
0644
edit
dl
rm
sha.html
13062
0644
edit
dl
rm
shelve.html
29955
0644
edit
dl
rm
shlex.html
35033
0644
edit
dl
rm
shutil.html
45454
0644
edit
dl
rm
signal.html
34023
0644
edit
dl
rm
simplehttpserver.html
20351
0644
edit
dl
rm
simplexmlrpcserver.html
37794
0644
edit
dl
rm
site.html
26887
0644
edit
dl
rm
smtpd.html
13587
0644
edit
dl
rm
smtplib.html
47054
0644
edit
dl
rm
sndhdr.html
10993
0644
edit
dl
rm
socket.html
116414
0644
edit
dl
rm
socketserver.html
76430
0644
edit
dl
rm
someos.html
16472
0644
edit
dl
rm
spwd.html
11163
0644
edit
dl
rm
sqlite3.html
150014
0644
edit
dl
rm
ssl.html
202453
0644
edit
dl
rm
stat.html
34597
0644
edit
dl
rm
statvfs.html
11326
0644
edit
dl
rm
stdtypes.html
298144
0644
edit
dl
rm
string.html
120219
0644
edit
dl
rm
stringio.html
20061
0644
edit
dl
rm
stringprep.html
17729
0644
edit
dl
rm
strings.html
15905
0644
edit
dl
rm
struct.html
44896
0644
edit
dl
rm
subprocess.html
110447
0644
edit
dl
rm
sun.html
7253
0644
edit
dl
rm
sunau.html
30011
0644
edit
dl
rm
sunaudio.html
19236
0644
edit
dl
rm
symbol.html
8140
0644
edit
dl
rm
symtable.html
25871
0644
edit
dl
rm
sys.html
110996
0644
edit
dl
rm
sysconfig.html
26299
0644
edit
dl
rm
syslog.html
19737
0644
edit
dl
rm
tabnanny.html
11393
0644
edit
dl
rm
tarfile.html
88728
0644
edit
dl
rm
telnetlib.html
27782
0644
edit
dl
rm
tempfile.html
31903
0644
edit
dl
rm
termios.html
17309
0644
edit
dl
rm
test.html
57030
0644
edit
dl
rm
textwrap.html
30135
0644
edit
dl
rm
thread.html
21486
0644
edit
dl
rm
threading.html
86655
0644
edit
dl
rm
time.html
63798
0644
edit
dl
rm
timeit.html
40529
0644
edit
dl
rm
tix.html
50582
0644
edit
dl
rm
tk.html
26568
0644
edit
dl
rm
tkinter.html
84316
0644
edit
dl
rm
token.html
20999
0644
edit
dl
rm
tokenize.html
20607
0644
edit
dl
rm
trace.html
28668
0644
edit
dl
rm
traceback.html
40900
0644
edit
dl
rm
ttk.html
108515
0644
edit
dl
rm
tty.html
9753
0644
edit
dl
rm
turtle.html
230483
0644
edit
dl
rm
types.html
29833
0644
edit
dl
rm
undoc.html
24680
0644
edit
dl
rm
unicodedata.html
20186
0644
edit
dl
rm
unittest.html
225021
0644
edit
dl
rm
unix.html
11223
0644
edit
dl
rm
urllib.html
68266
0644
edit
dl
rm
urllib2.html
113380
0644
edit
dl
rm
urlparse.html
43474
0644
edit
dl
rm
user.html
12707
0644
edit
dl
rm
userdict.html
32069
0644
edit
dl
rm
uu.html
11810
0644
edit
dl
rm
uuid.html
30137
0644
edit
dl
rm
warnings.html
50950
0644
edit
dl
rm
wave.html
24894
0644
edit
dl
rm
weakref.html
38808
0644
edit
dl
rm
webbrowser.html
26565
0644
edit
dl
rm
whichdb.html
9499
0644
edit
dl
rm
windows.html
9817
0644
edit
dl
rm
winsound.html
20466
0644
edit
dl
rm
wsgiref.html
88384
0644
edit
dl
rm
xdrlib.html
33018
0644
edit
dl
rm
xml.dom.html
97877
0644
edit
dl
rm
xml.dom.minidom.html
43230
0644
edit
dl
rm
xml.dom.pulldom.html
13835
0644
edit
dl
rm
xml.etree.elementtree.html
111804
0644
edit
dl
rm
xml.html
18007
0644
edit
dl
rm
xml.sax.handler.html
41877
0644
edit
dl
rm
xml.sax.html
23458
0644
edit
dl
rm
xml.sax.reader.html
44802
0644
edit
dl
rm
xml.sax.utils.html
16087
0644
edit
dl
rm
xmlrpclib.html
69191
0644
edit
dl
rm
zipfile.html
62227
0644
edit
dl
rm
zipimport.html
22769
0644
edit
dl
rm
zlib.html
31230
0644
edit
dl
rm
_winreg.html
64631
0644
edit
dl
rm
__builtin__.html
11069
0644
edit
dl
rm
__future__.html
14688
0644
edit
dl
rm
__main__.html
7512
0644
edit
dl
rm
Edit:
/usr/share/doc/python2-docs/html/library/heapq.html
(34890B)
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> <html xmlns="http://www.w3.org/1999/xhtml"> <head> <meta http-equiv="X-UA-Compatible" content="IE=Edge" /> <meta http-equiv="Content-Type" content="text/html; charset=utf-8" /> <title>8.4. heapq — Heap queue algorithm — Python 2.7.16 documentation</title> <link rel="stylesheet" href="../_static/classic.css" type="text/css" /> <link rel="stylesheet" href="../_static/pygments.css" type="text/css" /> <script type="text/javascript" id="documentation_options" data-url_root="../" src="../_static/documentation_options.js"></script> <script type="text/javascript" src="../_static/jquery.js"></script> <script type="text/javascript" src="../_static/underscore.js"></script> <script type="text/javascript" src="../_static/doctools.js"></script> <script type="text/javascript" src="../_static/sidebar.js"></script> <link rel="search" type="application/opensearchdescription+xml" title="Search within Python 2.7.16 documentation" href="../_static/opensearch.xml"/> <link rel="author" title="About these documents" href="../about.html" /> <link rel="index" title="Index" href="../genindex.html" /> <link rel="search" title="Search" href="../search.html" /> <link rel="copyright" title="Copyright" href="../copyright.html" /> <link rel="next" title="8.5. bisect — Array bisection algorithm" href="bisect.html" /> <link rel="prev" title="8.3. collections — High-performance container datatypes" href="collections.html" /> <link rel="shortcut icon" type="image/png" href="../_static/py.png" /> <link rel="canonical" href="https://docs.python.org/2/library/heapq.html" /> <script type="text/javascript" src="../_static/copybutton.js"></script> </head><body> <div class="related" role="navigation" aria-label="related navigation"> <h3>Navigation</h3> <ul> <li class="right" style="margin-right: 10px"> <a href="../genindex.html" title="General Index" accesskey="I">index</a></li> <li class="right" > <a href="../py-modindex.html" title="Python Module Index" >modules</a> |</li> <li class="right" > <a href="bisect.html" title="8.5. bisect — Array bisection algorithm" accesskey="N">next</a> |</li> <li class="right" > <a href="collections.html" title="8.3. collections — High-performance container datatypes" accesskey="P">previous</a> |</li> <li><img src="../_static/py.png" alt="" style="vertical-align: middle; margin-top: -1px"/></li> <li><a href="https://www.python.org/">Python</a> »</li> <li> <a href="../index.html">Python 2.7.16 documentation</a> » </li> <li class="nav-item nav-item-1"><a href="index.html" >The Python Standard Library</a> »</li> <li class="nav-item nav-item-2"><a href="datatypes.html" accesskey="U">8. Data Types</a> »</li> </ul> </div> <div class="document"> <div class="documentwrapper"> <div class="bodywrapper"> <div class="body" role="main"> <div class="section" id="module-heapq"> <span id="heapq-heap-queue-algorithm"></span><h1>8.4. <a class="reference internal" href="#module-heapq" title="heapq: Heap queue algorithm (a.k.a. priority queue)."><code class="xref py py-mod docutils literal notranslate"><span class="pre">heapq</span></code></a> — Heap queue algorithm<a class="headerlink" href="#module-heapq" title="Permalink to this headline">¶</a></h1> <div class="versionadded"> <p><span class="versionmodified">New in version 2.3.</span></p> </div> <p><strong>Source code:</strong> <a class="reference external" href="https://github.com/python/cpython/tree/2.7/Lib/heapq.py">Lib/heapq.py</a></p> <hr class="docutils" /> <p>This module provides an implementation of the heap queue algorithm, also known as the priority queue algorithm.</p> <p>Heaps are binary trees for which every parent node has a value less than or equal to any of its children. This implementation uses arrays for which <code class="docutils literal notranslate"><span class="pre">heap[k]</span> <span class="pre"><=</span> <span class="pre">heap[2*k+1]</span></code> and <code class="docutils literal notranslate"><span class="pre">heap[k]</span> <span class="pre"><=</span> <span class="pre">heap[2*k+2]</span></code> for all <em>k</em>, counting elements from zero. For the sake of comparison, non-existing elements are considered to be infinite. The interesting property of a heap is that its smallest element is always the root, <code class="docutils literal notranslate"><span class="pre">heap[0]</span></code>.</p> <p>The API below differs from textbook heap algorithms in two aspects: (a) We use zero-based indexing. This makes the relationship between the index for a node and the indexes for its children slightly less obvious, but is more suitable since Python uses zero-based indexing. (b) Our pop method returns the smallest item, not the largest (called a “min heap” in textbooks; a “max heap” is more common in texts because of its suitability for in-place sorting).</p> <p>These two make it possible to view the heap as a regular Python list without surprises: <code class="docutils literal notranslate"><span class="pre">heap[0]</span></code> is the smallest item, and <code class="docutils literal notranslate"><span class="pre">heap.sort()</span></code> maintains the heap invariant!</p> <p>To create a heap, use a list initialized to <code class="docutils literal notranslate"><span class="pre">[]</span></code>, or you can transform a populated list into a heap via function <a class="reference internal" href="#heapq.heapify" title="heapq.heapify"><code class="xref py py-func docutils literal notranslate"><span class="pre">heapify()</span></code></a>.</p> <p>The following functions are provided:</p> <dl class="function"> <dt id="heapq.heappush"> <code class="descclassname">heapq.</code><code class="descname">heappush</code><span class="sig-paren">(</span><em>heap</em>, <em>item</em><span class="sig-paren">)</span><a class="headerlink" href="#heapq.heappush" title="Permalink to this definition">¶</a></dt> <dd><p>Push the value <em>item</em> onto the <em>heap</em>, maintaining the heap invariant.</p> </dd></dl> <dl class="function"> <dt id="heapq.heappop"> <code class="descclassname">heapq.</code><code class="descname">heappop</code><span class="sig-paren">(</span><em>heap</em><span class="sig-paren">)</span><a class="headerlink" href="#heapq.heappop" title="Permalink to this definition">¶</a></dt> <dd><p>Pop and return the smallest item from the <em>heap</em>, maintaining the heap invariant. If the heap is empty, <a class="reference internal" href="exceptions.html#exceptions.IndexError" title="exceptions.IndexError"><code class="xref py py-exc docutils literal notranslate"><span class="pre">IndexError</span></code></a> is raised. To access the smallest item without popping it, use <code class="docutils literal notranslate"><span class="pre">heap[0]</span></code>.</p> </dd></dl> <dl class="function"> <dt id="heapq.heappushpop"> <code class="descclassname">heapq.</code><code class="descname">heappushpop</code><span class="sig-paren">(</span><em>heap</em>, <em>item</em><span class="sig-paren">)</span><a class="headerlink" href="#heapq.heappushpop" title="Permalink to this definition">¶</a></dt> <dd><p>Push <em>item</em> on the heap, then pop and return the smallest item from the <em>heap</em>. The combined action runs more efficiently than <a class="reference internal" href="#heapq.heappush" title="heapq.heappush"><code class="xref py py-func docutils literal notranslate"><span class="pre">heappush()</span></code></a> followed by a separate call to <a class="reference internal" href="#heapq.heappop" title="heapq.heappop"><code class="xref py py-func docutils literal notranslate"><span class="pre">heappop()</span></code></a>.</p> <div class="versionadded"> <p><span class="versionmodified">New in version 2.6.</span></p> </div> </dd></dl> <dl class="function"> <dt id="heapq.heapify"> <code class="descclassname">heapq.</code><code class="descname">heapify</code><span class="sig-paren">(</span><em>x</em><span class="sig-paren">)</span><a class="headerlink" href="#heapq.heapify" title="Permalink to this definition">¶</a></dt> <dd><p>Transform list <em>x</em> into a heap, in-place, in linear time.</p> </dd></dl> <dl class="function"> <dt id="heapq.heapreplace"> <code class="descclassname">heapq.</code><code class="descname">heapreplace</code><span class="sig-paren">(</span><em>heap</em>, <em>item</em><span class="sig-paren">)</span><a class="headerlink" href="#heapq.heapreplace" title="Permalink to this definition">¶</a></dt> <dd><p>Pop and return the smallest item from the <em>heap</em>, and also push the new <em>item</em>. The heap size doesn’t change. If the heap is empty, <a class="reference internal" href="exceptions.html#exceptions.IndexError" title="exceptions.IndexError"><code class="xref py py-exc docutils literal notranslate"><span class="pre">IndexError</span></code></a> is raised.</p> <p>This one step operation is more efficient than a <a class="reference internal" href="#heapq.heappop" title="heapq.heappop"><code class="xref py py-func docutils literal notranslate"><span class="pre">heappop()</span></code></a> followed by <a class="reference internal" href="#heapq.heappush" title="heapq.heappush"><code class="xref py py-func docutils literal notranslate"><span class="pre">heappush()</span></code></a> and can be more appropriate when using a fixed-size heap. The pop/push combination always returns an element from the heap and replaces it with <em>item</em>.</p> <p>The value returned may be larger than the <em>item</em> added. If that isn’t desired, consider using <a class="reference internal" href="#heapq.heappushpop" title="heapq.heappushpop"><code class="xref py py-func docutils literal notranslate"><span class="pre">heappushpop()</span></code></a> instead. Its push/pop combination returns the smaller of the two values, leaving the larger value on the heap.</p> </dd></dl> <p>The module also offers three general purpose functions based on heaps.</p> <dl class="function"> <dt id="heapq.merge"> <code class="descclassname">heapq.</code><code class="descname">merge</code><span class="sig-paren">(</span><em>*iterables</em><span class="sig-paren">)</span><a class="headerlink" href="#heapq.merge" title="Permalink to this definition">¶</a></dt> <dd><p>Merge multiple sorted inputs into a single sorted output (for example, merge timestamped entries from multiple log files). Returns an <a class="reference internal" href="../glossary.html#term-iterator"><span class="xref std std-term">iterator</span></a> over the sorted values.</p> <p>Similar to <code class="docutils literal notranslate"><span class="pre">sorted(itertools.chain(*iterables))</span></code> but returns an iterable, does not pull the data into memory all at once, and assumes that each of the input streams is already sorted (smallest to largest).</p> <div class="versionadded"> <p><span class="versionmodified">New in version 2.6.</span></p> </div> </dd></dl> <dl class="function"> <dt id="heapq.nlargest"> <code class="descclassname">heapq.</code><code class="descname">nlargest</code><span class="sig-paren">(</span><em>n</em>, <em>iterable</em><span class="optional">[</span>, <em>key</em><span class="optional">]</span><span class="sig-paren">)</span><a class="headerlink" href="#heapq.nlargest" title="Permalink to this definition">¶</a></dt> <dd><p>Return a list with the <em>n</em> largest elements from the dataset defined by <em>iterable</em>. <em>key</em>, if provided, specifies a function of one argument that is used to extract a comparison key from each element in the iterable: <code class="docutils literal notranslate"><span class="pre">key=str.lower</span></code> Equivalent to: <code class="docutils literal notranslate"><span class="pre">sorted(iterable,</span> <span class="pre">key=key,</span> <span class="pre">reverse=True)[:n]</span></code></p> <div class="versionadded"> <p><span class="versionmodified">New in version 2.4.</span></p> </div> <div class="versionchanged"> <p><span class="versionmodified">Changed in version 2.5: </span>Added the optional <em>key</em> argument.</p> </div> </dd></dl> <dl class="function"> <dt id="heapq.nsmallest"> <code class="descclassname">heapq.</code><code class="descname">nsmallest</code><span class="sig-paren">(</span><em>n</em>, <em>iterable</em><span class="optional">[</span>, <em>key</em><span class="optional">]</span><span class="sig-paren">)</span><a class="headerlink" href="#heapq.nsmallest" title="Permalink to this definition">¶</a></dt> <dd><p>Return a list with the <em>n</em> smallest elements from the dataset defined by <em>iterable</em>. <em>key</em>, if provided, specifies a function of one argument that is used to extract a comparison key from each element in the iterable: <code class="docutils literal notranslate"><span class="pre">key=str.lower</span></code> Equivalent to: <code class="docutils literal notranslate"><span class="pre">sorted(iterable,</span> <span class="pre">key=key)[:n]</span></code></p> <div class="versionadded"> <p><span class="versionmodified">New in version 2.4.</span></p> </div> <div class="versionchanged"> <p><span class="versionmodified">Changed in version 2.5: </span>Added the optional <em>key</em> argument.</p> </div> </dd></dl> <p>The latter two functions perform best for smaller values of <em>n</em>. For larger values, it is more efficient to use the <a class="reference internal" href="functions.html#sorted" title="sorted"><code class="xref py py-func docutils literal notranslate"><span class="pre">sorted()</span></code></a> function. Also, when <code class="docutils literal notranslate"><span class="pre">n==1</span></code>, it is more efficient to use the built-in <a class="reference internal" href="functions.html#min" title="min"><code class="xref py py-func docutils literal notranslate"><span class="pre">min()</span></code></a> and <a class="reference internal" href="functions.html#max" title="max"><code class="xref py py-func docutils literal notranslate"><span class="pre">max()</span></code></a> functions. If repeated usage of these functions is required, consider turning the iterable into an actual heap.</p> <div class="section" id="basic-examples"> <h2>8.4.1. Basic Examples<a class="headerlink" href="#basic-examples" title="Permalink to this headline">¶</a></h2> <p>A <a class="reference external" href="https://en.wikipedia.org/wiki/Heapsort">heapsort</a> can be implemented by pushing all values onto a heap and then popping off the smallest values one at a time:</p> <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">>>> </span><span class="k">def</span> <span class="nf">heapsort</span><span class="p">(</span><span class="n">iterable</span><span class="p">):</span> <span class="gp">... </span> <span class="n">h</span> <span class="o">=</span> <span class="p">[]</span> <span class="gp">... </span> <span class="k">for</span> <span class="n">value</span> <span class="ow">in</span> <span class="n">iterable</span><span class="p">:</span> <span class="gp">... </span> <span class="n">heappush</span><span class="p">(</span><span class="n">h</span><span class="p">,</span> <span class="n">value</span><span class="p">)</span> <span class="gp">... </span> <span class="k">return</span> <span class="p">[</span><span class="n">heappop</span><span class="p">(</span><span class="n">h</span><span class="p">)</span> <span class="k">for</span> <span class="n">i</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="nb">len</span><span class="p">(</span><span class="n">h</span><span class="p">))]</span> <span class="gp">...</span> <span class="gp">>>> </span><span class="n">heapsort</span><span class="p">([</span><span class="mi">1</span><span class="p">,</span> <span class="mi">3</span><span class="p">,</span> <span class="mi">5</span><span class="p">,</span> <span class="mi">7</span><span class="p">,</span> <span class="mi">9</span><span class="p">,</span> <span class="mi">2</span><span class="p">,</span> <span class="mi">4</span><span class="p">,</span> <span class="mi">6</span><span class="p">,</span> <span class="mi">8</span><span class="p">,</span> <span class="mi">0</span><span class="p">])</span> <span class="go">[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]</span> </pre></div> </div> <p>This is similar to <code class="docutils literal notranslate"><span class="pre">sorted(iterable)</span></code>, but unlike <a class="reference internal" href="functions.html#sorted" title="sorted"><code class="xref py py-func docutils literal notranslate"><span class="pre">sorted()</span></code></a>, this implementation is not stable.</p> <p>Heap elements can be tuples. This is useful for assigning comparison values (such as task priorities) alongside the main record being tracked:</p> <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">>>> </span><span class="n">h</span> <span class="o">=</span> <span class="p">[]</span> <span class="gp">>>> </span><span class="n">heappush</span><span class="p">(</span><span class="n">h</span><span class="p">,</span> <span class="p">(</span><span class="mi">5</span><span class="p">,</span> <span class="s1">'write code'</span><span class="p">))</span> <span class="gp">>>> </span><span class="n">heappush</span><span class="p">(</span><span class="n">h</span><span class="p">,</span> <span class="p">(</span><span class="mi">7</span><span class="p">,</span> <span class="s1">'release product'</span><span class="p">))</span> <span class="gp">>>> </span><span class="n">heappush</span><span class="p">(</span><span class="n">h</span><span class="p">,</span> <span class="p">(</span><span class="mi">1</span><span class="p">,</span> <span class="s1">'write spec'</span><span class="p">))</span> <span class="gp">>>> </span><span class="n">heappush</span><span class="p">(</span><span class="n">h</span><span class="p">,</span> <span class="p">(</span><span class="mi">3</span><span class="p">,</span> <span class="s1">'create tests'</span><span class="p">))</span> <span class="gp">>>> </span><span class="n">heappop</span><span class="p">(</span><span class="n">h</span><span class="p">)</span> <span class="go">(1, 'write spec')</span> </pre></div> </div> </div> <div class="section" id="priority-queue-implementation-notes"> <h2>8.4.2. Priority Queue Implementation Notes<a class="headerlink" href="#priority-queue-implementation-notes" title="Permalink to this headline">¶</a></h2> <p>A <a class="reference external" href="https://en.wikipedia.org/wiki/Priority_queue">priority queue</a> is common use for a heap, and it presents several implementation challenges:</p> <ul class="simple"> <li>Sort stability: how do you get two tasks with equal priorities to be returned in the order they were originally added?</li> <li>In the future with Python 3, tuple comparison breaks for (priority, task) pairs if the priorities are equal and the tasks do not have a default comparison order.</li> <li>If the priority of a task changes, how do you move it to a new position in the heap?</li> <li>Or if a pending task needs to be deleted, how do you find it and remove it from the queue?</li> </ul> <p>A solution to the first two challenges is to store entries as 3-element list including the priority, an entry count, and the task. The entry count serves as a tie-breaker so that two tasks with the same priority are returned in the order they were added. And since no two entry counts are the same, the tuple comparison will never attempt to directly compare two tasks.</p> <p>The remaining challenges revolve around finding a pending task and making changes to its priority or removing it entirely. Finding a task can be done with a dictionary pointing to an entry in the queue.</p> <p>Removing the entry or changing its priority is more difficult because it would break the heap structure invariants. So, a possible solution is to mark the existing entry as removed and add a new entry with the revised priority:</p> <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">pq</span> <span class="o">=</span> <span class="p">[]</span> <span class="c1"># list of entries arranged in a heap</span> <span class="n">entry_finder</span> <span class="o">=</span> <span class="p">{}</span> <span class="c1"># mapping of tasks to entries</span> <span class="n">REMOVED</span> <span class="o">=</span> <span class="s1">'<removed-task>'</span> <span class="c1"># placeholder for a removed task</span> <span class="n">counter</span> <span class="o">=</span> <span class="n">itertools</span><span class="o">.</span><span class="n">count</span><span class="p">()</span> <span class="c1"># unique sequence count</span> <span class="k">def</span> <span class="nf">add_task</span><span class="p">(</span><span class="n">task</span><span class="p">,</span> <span class="n">priority</span><span class="o">=</span><span class="mi">0</span><span class="p">):</span> <span class="s1">'Add a new task or update the priority of an existing task'</span> <span class="k">if</span> <span class="n">task</span> <span class="ow">in</span> <span class="n">entry_finder</span><span class="p">:</span> <span class="n">remove_task</span><span class="p">(</span><span class="n">task</span><span class="p">)</span> <span class="n">count</span> <span class="o">=</span> <span class="nb">next</span><span class="p">(</span><span class="n">counter</span><span class="p">)</span> <span class="n">entry</span> <span class="o">=</span> <span class="p">[</span><span class="n">priority</span><span class="p">,</span> <span class="n">count</span><span class="p">,</span> <span class="n">task</span><span class="p">]</span> <span class="n">entry_finder</span><span class="p">[</span><span class="n">task</span><span class="p">]</span> <span class="o">=</span> <span class="n">entry</span> <span class="n">heappush</span><span class="p">(</span><span class="n">pq</span><span class="p">,</span> <span class="n">entry</span><span class="p">)</span> <span class="k">def</span> <span class="nf">remove_task</span><span class="p">(</span><span class="n">task</span><span class="p">):</span> <span class="s1">'Mark an existing task as REMOVED. Raise KeyError if not found.'</span> <span class="n">entry</span> <span class="o">=</span> <span class="n">entry_finder</span><span class="o">.</span><span class="n">pop</span><span class="p">(</span><span class="n">task</span><span class="p">)</span> <span class="n">entry</span><span class="p">[</span><span class="o">-</span><span class="mi">1</span><span class="p">]</span> <span class="o">=</span> <span class="n">REMOVED</span> <span class="k">def</span> <span class="nf">pop_task</span><span class="p">():</span> <span class="s1">'Remove and return the lowest priority task. Raise KeyError if empty.'</span> <span class="k">while</span> <span class="n">pq</span><span class="p">:</span> <span class="n">priority</span><span class="p">,</span> <span class="n">count</span><span class="p">,</span> <span class="n">task</span> <span class="o">=</span> <span class="n">heappop</span><span class="p">(</span><span class="n">pq</span><span class="p">)</span> <span class="k">if</span> <span class="n">task</span> <span class="ow">is</span> <span class="ow">not</span> <span class="n">REMOVED</span><span class="p">:</span> <span class="k">del</span> <span class="n">entry_finder</span><span class="p">[</span><span class="n">task</span><span class="p">]</span> <span class="k">return</span> <span class="n">task</span> <span class="k">raise</span> <span class="ne">KeyError</span><span class="p">(</span><span class="s1">'pop from an empty priority queue'</span><span class="p">)</span> </pre></div> </div> </div> <div class="section" id="theory"> <h2>8.4.3. Theory<a class="headerlink" href="#theory" title="Permalink to this headline">¶</a></h2> <p>Heaps are arrays for which <code class="docutils literal notranslate"><span class="pre">a[k]</span> <span class="pre"><=</span> <span class="pre">a[2*k+1]</span></code> and <code class="docutils literal notranslate"><span class="pre">a[k]</span> <span class="pre"><=</span> <span class="pre">a[2*k+2]</span></code> for all <em>k</em>, counting elements from 0. For the sake of comparison, non-existing elements are considered to be infinite. The interesting property of a heap is that <code class="docutils literal notranslate"><span class="pre">a[0]</span></code> is always its smallest element.</p> <p>The strange invariant above is meant to be an efficient memory representation for a tournament. The numbers below are <em>k</em>, not <code class="docutils literal notranslate"><span class="pre">a[k]</span></code>:</p> <div class="highlight-default notranslate"><div class="highlight"><pre><span></span> <span class="mi">0</span> <span class="mi">1</span> <span class="mi">2</span> <span class="mi">3</span> <span class="mi">4</span> <span class="mi">5</span> <span class="mi">6</span> <span class="mi">7</span> <span class="mi">8</span> <span class="mi">9</span> <span class="mi">10</span> <span class="mi">11</span> <span class="mi">12</span> <span class="mi">13</span> <span class="mi">14</span> <span class="mi">15</span> <span class="mi">16</span> <span class="mi">17</span> <span class="mi">18</span> <span class="mi">19</span> <span class="mi">20</span> <span class="mi">21</span> <span class="mi">22</span> <span class="mi">23</span> <span class="mi">24</span> <span class="mi">25</span> <span class="mi">26</span> <span class="mi">27</span> <span class="mi">28</span> <span class="mi">29</span> <span class="mi">30</span> </pre></div> </div> <p>In the tree above, each cell <em>k</em> is topping <code class="docutils literal notranslate"><span class="pre">2*k+1</span></code> and <code class="docutils literal notranslate"><span class="pre">2*k+2</span></code>. In a usual binary tournament we see in sports, each cell is the winner over the two cells it tops, and we can trace the winner down the tree to see all opponents s/he had. However, in many computer applications of such tournaments, we do not need to trace the history of a winner. To be more memory efficient, when a winner is promoted, we try to replace it by something else at a lower level, and the rule becomes that a cell and the two cells it tops contain three different items, but the top cell “wins” over the two topped cells.</p> <p>If this heap invariant is protected at all time, index 0 is clearly the overall winner. The simplest algorithmic way to remove it and find the “next” winner is to move some loser (let’s say cell 30 in the diagram above) into the 0 position, and then percolate this new 0 down the tree, exchanging values, until the invariant is re-established. This is clearly logarithmic on the total number of items in the tree. By iterating over all items, you get an O(n log n) sort.</p> <p>A nice feature of this sort is that you can efficiently insert new items while the sort is going on, provided that the inserted items are not “better” than the last 0’th element you extracted. This is especially useful in simulation contexts, where the tree holds all incoming events, and the “win” condition means the smallest scheduled time. When an event schedules other events for execution, they are scheduled into the future, so they can easily go into the heap. So, a heap is a good structure for implementing schedulers (this is what I used for my MIDI sequencer :-).</p> <p>Various structures for implementing schedulers have been extensively studied, and heaps are good for this, as they are reasonably speedy, the speed is almost constant, and the worst case is not much different than the average case. However, there are other representations which are more efficient overall, yet the worst cases might be terrible.</p> <p>Heaps are also very useful in big disk sorts. You most probably all know that a big sort implies producing “runs” (which are pre-sorted sequences, whose size is usually related to the amount of CPU memory), followed by a merging passes for these runs, which merging is often very cleverly organised <a class="footnote-reference" href="#id2" id="id1">[1]</a>. It is very important that the initial sort produces the longest runs possible. Tournaments are a good way to achieve that. If, using all the memory available to hold a tournament, you replace and percolate items that happen to fit the current run, you’ll produce runs which are twice the size of the memory for random input, and much better for input fuzzily ordered.</p> <p>Moreover, if you output the 0’th item on disk and get an input which may not fit in the current tournament (because the value “wins” over the last output value), it cannot fit in the heap, so the size of the heap decreases. The freed memory could be cleverly reused immediately for progressively building a second heap, which grows at exactly the same rate the first heap is melting. When the first heap completely vanishes, you switch heaps and start a new run. Clever and quite effective!</p> <p>In a word, heaps are useful memory structures to know. I use them in a few applications, and I think it is good to keep a ‘heap’ module around. :-)</p> <p class="rubric">Footnotes</p> <table class="docutils footnote" frame="void" id="id2" rules="none"> <colgroup><col class="label" /><col /></colgroup> <tbody valign="top"> <tr><td class="label"><a class="fn-backref" href="#id1">[1]</a></td><td>The disk balancing algorithms which are current, nowadays, are more annoying than clever, and this is a consequence of the seeking capabilities of the disks. On devices which cannot seek, like big tape drives, the story was quite different, and one had to be very clever to ensure (far in advance) that each tape movement will be the most effective possible (that is, will best participate at “progressing” the merge). Some tapes were even able to read backwards, and this was also used to avoid the rewinding time. Believe me, real good tape sorts were quite spectacular to watch! From all times, sorting has always been a Great Art! :-)</td></tr> </tbody> </table> </div> </div> </div> </div> </div> <div class="sphinxsidebar" role="navigation" aria-label="main navigation"> <div class="sphinxsidebarwrapper"> <h3><a href="../contents.html">Table Of Contents</a></h3> <ul> <li><a class="reference internal" href="#">8.4. <code class="docutils literal notranslate"><span class="pre">heapq</span></code> — Heap queue algorithm</a><ul> <li><a class="reference internal" href="#basic-examples">8.4.1. Basic Examples</a></li> <li><a class="reference internal" href="#priority-queue-implementation-notes">8.4.2. Priority Queue Implementation Notes</a></li> <li><a class="reference internal" href="#theory">8.4.3. Theory</a></li> </ul> </li> </ul> <h4>Previous topic</h4> <p class="topless"><a href="collections.html" title="previous chapter">8.3. <code class="docutils literal notranslate"><span class="pre">collections</span></code> — High-performance container datatypes</a></p> <h4>Next topic</h4> <p class="topless"><a href="bisect.html" title="next chapter">8.5. <code class="docutils literal notranslate"><span class="pre">bisect</span></code> — Array bisection algorithm</a></p> <div role="note" aria-label="source link"> <h3>This Page</h3> <ul class="this-page-menu"> <li><a href="../_sources/library/heapq.rst.txt" rel="nofollow">Show Source</a></li> </ul> </div> <div id="searchbox" style="display: none" role="search"> <h3>Quick search</h3> <div class="searchformwrapper"> <form class="search" action="../search.html" method="get"> <input type="text" name="q" /> <input type="submit" value="Go" /> <input type="hidden" name="check_keywords" value="yes" /> <input type="hidden" name="area" value="default" /> </form> </div> </div> <script type="text/javascript">$('#searchbox').show(0);</script> </div> </div> <div class="clearer"></div> </div> <div class="related" role="navigation" aria-label="related navigation"> <h3>Navigation</h3> <ul> <li class="right" style="margin-right: 10px"> <a href="../genindex.html" title="General Index" >index</a></li> <li class="right" > <a href="../py-modindex.html" title="Python Module Index" >modules</a> |</li> <li class="right" > <a href="bisect.html" title="8.5. bisect — Array bisection algorithm" >next</a> |</li> <li class="right" > <a href="collections.html" title="8.3. collections — High-performance container datatypes" >previous</a> |</li> <li><img src="../_static/py.png" alt="" style="vertical-align: middle; margin-top: -1px"/></li> <li><a href="https://www.python.org/">Python</a> »</li> <li> <a href="../index.html">Python 2.7.16 documentation</a> » </li> <li class="nav-item nav-item-1"><a href="index.html" >The Python Standard Library</a> »</li> <li class="nav-item nav-item-2"><a href="datatypes.html" >8. Data Types</a> »</li> </ul> </div> <div class="footer"> © <a href="../copyright.html">Copyright</a> 1990-2019, Python Software Foundation. <br /> The Python Software Foundation is a non-profit corporation. <a href="https://www.python.org/psf/donations/">Please donate.</a> <br /> Last updated on Mar 27, 2019. <a href="../bugs.html">Found a bug</a>? <br /> Created using <a href="http://sphinx.pocoo.org/">Sphinx</a> 1.7.6. </div> </body> </html>
Save
cmd:
run