1
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
2
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
5
<html xmlns="http://www.w3.org/1999/xhtml">
7
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
9
<title>8.4. heapq — Heap queue algorithm — Python 2.7.10 documentation</title>
11
<link rel="stylesheet" href="../_static/default.css" type="text/css" />
12
<link rel="stylesheet" href="../_static/pygments.css" type="text/css" />
14
<script type="text/javascript">
15
var DOCUMENTATION_OPTIONS = {
18
COLLAPSE_INDEX: false,
23
<script type="text/javascript" src="../_static/jquery.js"></script>
24
<script type="text/javascript" src="../_static/underscore.js"></script>
25
<script type="text/javascript" src="../_static/doctools.js"></script>
26
<script type="text/javascript" src="../_static/sidebar.js"></script>
27
<link rel="search" type="application/opensearchdescription+xml"
28
title="Search within Python 2.7.10 documentation"
29
href="../_static/opensearch.xml"/>
30
<link rel="author" title="About these documents" href="../about.html" />
31
<link rel="copyright" title="Copyright" href="../copyright.html" />
32
<link rel="top" title="Python 2.7.10 documentation" href="../index.html" />
33
<link rel="up" title="8. Data Types" href="datatypes.html" />
34
<link rel="next" title="8.5. bisect — Array bisection algorithm" href="bisect.html" />
35
<link rel="prev" title="8.3. collections — High-performance container datatypes" href="collections.html" />
36
<link rel="shortcut icon" type="image/png" href="../_static/py.png" />
37
<script type="text/javascript" src="../_static/copybutton.js"></script>
38
<script type="text/javascript" src="../_static/version_switch.js"></script>
47
<li class="right" style="margin-right: 10px">
48
<a href="../genindex.html" title="General Index"
49
accesskey="I">index</a></li>
51
<a href="../py-modindex.html" title="Python Module Index"
54
<a href="bisect.html" title="8.5. bisect — Array bisection algorithm"
55
accesskey="N">next</a> |</li>
57
<a href="collections.html" title="8.3. collections — High-performance container datatypes"
58
accesskey="P">previous</a> |</li>
59
<li><img src="../_static/py.png" alt=""
60
style="vertical-align: middle; margin-top: -1px"/></li>
61
<li><a href="https://www.python.org/">Python</a> »</li>
63
<span class="version_switcher_placeholder">2.7.10</span>
64
<a href="../index.html">Documentation</a> »
67
<li><a href="index.html" >The Python Standard Library</a> »</li>
68
<li><a href="datatypes.html" accesskey="U">8. Data Types</a> »</li>
72
<div class="document">
73
<div class="documentwrapper">
74
<div class="bodywrapper">
77
<div class="section" id="module-heapq">
78
<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)."><tt class="xref py py-mod docutils literal"><span class="pre">heapq</span></tt></a> — Heap queue algorithm<a class="headerlink" href="#module-heapq" title="Permalink to this headline">¶</a></h1>
79
<div class="versionadded">
80
<p><span class="versionmodified">New in version 2.3.</span></p>
82
<p><strong>Source code:</strong> <a class="reference external" href="https://hg.python.org/cpython/file/2.7/Lib/heapq.py">Lib/heapq.py</a></p>
83
<hr class="docutils" />
84
<p>This module provides an implementation of the heap queue algorithm, also known
85
as the priority queue algorithm.</p>
86
<p>Heaps are binary trees for which every parent node has a value less than or
87
equal to any of its children. This implementation uses arrays for which
88
<tt class="docutils literal"><span class="pre">heap[k]</span> <span class="pre"><=</span> <span class="pre">heap[2*k+1]</span></tt> and <tt class="docutils literal"><span class="pre">heap[k]</span> <span class="pre"><=</span> <span class="pre">heap[2*k+2]</span></tt> for all <em>k</em>, counting
89
elements from zero. For the sake of comparison, non-existing elements are
90
considered to be infinite. The interesting property of a heap is that its
91
smallest element is always the root, <tt class="docutils literal"><span class="pre">heap[0]</span></tt>.</p>
92
<p>The API below differs from textbook heap algorithms in two aspects: (a) We use
93
zero-based indexing. This makes the relationship between the index for a node
94
and the indexes for its children slightly less obvious, but is more suitable
95
since Python uses zero-based indexing. (b) Our pop method returns the smallest
96
item, not the largest (called a “min heap” in textbooks; a “max heap” is more
97
common in texts because of its suitability for in-place sorting).</p>
98
<p>These two make it possible to view the heap as a regular Python list without
99
surprises: <tt class="docutils literal"><span class="pre">heap[0]</span></tt> is the smallest item, and <tt class="docutils literal"><span class="pre">heap.sort()</span></tt> maintains the
101
<p>To create a heap, use a list initialized to <tt class="docutils literal"><span class="pre">[]</span></tt>, or you can transform a
102
populated list into a heap via function <a class="reference internal" href="#heapq.heapify" title="heapq.heapify"><tt class="xref py py-func docutils literal"><span class="pre">heapify()</span></tt></a>.</p>
103
<p>The following functions are provided:</p>
104
<dl class="function">
105
<dt id="heapq.heappush">
106
<tt class="descclassname">heapq.</tt><tt class="descname">heappush</tt><big>(</big><em>heap</em>, <em>item</em><big>)</big><a class="headerlink" href="#heapq.heappush" title="Permalink to this definition">¶</a></dt>
107
<dd><p>Push the value <em>item</em> onto the <em>heap</em>, maintaining the heap invariant.</p>
110
<dl class="function">
111
<dt id="heapq.heappop">
112
<tt class="descclassname">heapq.</tt><tt class="descname">heappop</tt><big>(</big><em>heap</em><big>)</big><a class="headerlink" href="#heapq.heappop" title="Permalink to this definition">¶</a></dt>
113
<dd><p>Pop and return the smallest item from the <em>heap</em>, maintaining the heap
114
invariant. If the heap is empty, <a class="reference internal" href="exceptions.html#exceptions.IndexError" title="exceptions.IndexError"><tt class="xref py py-exc docutils literal"><span class="pre">IndexError</span></tt></a> is raised. To access the
115
smallest item without popping it, use <tt class="docutils literal"><span class="pre">heap[0]</span></tt>.</p>
118
<dl class="function">
119
<dt id="heapq.heappushpop">
120
<tt class="descclassname">heapq.</tt><tt class="descname">heappushpop</tt><big>(</big><em>heap</em>, <em>item</em><big>)</big><a class="headerlink" href="#heapq.heappushpop" title="Permalink to this definition">¶</a></dt>
121
<dd><p>Push <em>item</em> on the heap, then pop and return the smallest item from the
122
<em>heap</em>. The combined action runs more efficiently than <a class="reference internal" href="#heapq.heappush" title="heapq.heappush"><tt class="xref py py-func docutils literal"><span class="pre">heappush()</span></tt></a>
123
followed by a separate call to <a class="reference internal" href="#heapq.heappop" title="heapq.heappop"><tt class="xref py py-func docutils literal"><span class="pre">heappop()</span></tt></a>.</p>
124
<div class="versionadded">
125
<p><span class="versionmodified">New in version 2.6.</span></p>
129
<dl class="function">
130
<dt id="heapq.heapify">
131
<tt class="descclassname">heapq.</tt><tt class="descname">heapify</tt><big>(</big><em>x</em><big>)</big><a class="headerlink" href="#heapq.heapify" title="Permalink to this definition">¶</a></dt>
132
<dd><p>Transform list <em>x</em> into a heap, in-place, in linear time.</p>
135
<dl class="function">
136
<dt id="heapq.heapreplace">
137
<tt class="descclassname">heapq.</tt><tt class="descname">heapreplace</tt><big>(</big><em>heap</em>, <em>item</em><big>)</big><a class="headerlink" href="#heapq.heapreplace" title="Permalink to this definition">¶</a></dt>
138
<dd><p>Pop and return the smallest item from the <em>heap</em>, and also push the new <em>item</em>.
139
The heap size doesn’t change. If the heap is empty, <a class="reference internal" href="exceptions.html#exceptions.IndexError" title="exceptions.IndexError"><tt class="xref py py-exc docutils literal"><span class="pre">IndexError</span></tt></a> is raised.</p>
140
<p>This one step operation is more efficient than a <a class="reference internal" href="#heapq.heappop" title="heapq.heappop"><tt class="xref py py-func docutils literal"><span class="pre">heappop()</span></tt></a> followed by
141
<a class="reference internal" href="#heapq.heappush" title="heapq.heappush"><tt class="xref py py-func docutils literal"><span class="pre">heappush()</span></tt></a> and can be more appropriate when using a fixed-size heap.
142
The pop/push combination always returns an element from the heap and replaces
143
it with <em>item</em>.</p>
144
<p>The value returned may be larger than the <em>item</em> added. If that isn’t
145
desired, consider using <a class="reference internal" href="#heapq.heappushpop" title="heapq.heappushpop"><tt class="xref py py-func docutils literal"><span class="pre">heappushpop()</span></tt></a> instead. Its push/pop
146
combination returns the smaller of the two values, leaving the larger value
150
<p>The module also offers three general purpose functions based on heaps.</p>
151
<dl class="function">
152
<dt id="heapq.merge">
153
<tt class="descclassname">heapq.</tt><tt class="descname">merge</tt><big>(</big><em>*iterables</em><big>)</big><a class="headerlink" href="#heapq.merge" title="Permalink to this definition">¶</a></dt>
154
<dd><p>Merge multiple sorted inputs into a single sorted output (for example, merge
155
timestamped entries from multiple log files). Returns an <a class="reference internal" href="../glossary.html#term-iterator"><em class="xref std std-term">iterator</em></a>
156
over the sorted values.</p>
157
<p>Similar to <tt class="docutils literal"><span class="pre">sorted(itertools.chain(*iterables))</span></tt> but returns an iterable, does
158
not pull the data into memory all at once, and assumes that each of the input
159
streams is already sorted (smallest to largest).</p>
160
<div class="versionadded">
161
<p><span class="versionmodified">New in version 2.6.</span></p>
165
<dl class="function">
166
<dt id="heapq.nlargest">
167
<tt class="descclassname">heapq.</tt><tt class="descname">nlargest</tt><big>(</big><em>n</em>, <em>iterable</em><span class="optional">[</span>, <em>key</em><span class="optional">]</span><big>)</big><a class="headerlink" href="#heapq.nlargest" title="Permalink to this definition">¶</a></dt>
168
<dd><p>Return a list with the <em>n</em> largest elements from the dataset defined by
169
<em>iterable</em>. <em>key</em>, if provided, specifies a function of one argument that is
170
used to extract a comparison key from each element in the iterable:
171
<tt class="docutils literal"><span class="pre">key=str.lower</span></tt> Equivalent to: <tt class="docutils literal"><span class="pre">sorted(iterable,</span> <span class="pre">key=key,</span>
172
<span class="pre">reverse=True)[:n]</span></tt></p>
173
<div class="versionadded">
174
<p><span class="versionmodified">New in version 2.4.</span></p>
176
<div class="versionchanged">
177
<p><span class="versionmodified">Changed in version 2.5: </span>Added the optional <em>key</em> argument.</p>
181
<dl class="function">
182
<dt id="heapq.nsmallest">
183
<tt class="descclassname">heapq.</tt><tt class="descname">nsmallest</tt><big>(</big><em>n</em>, <em>iterable</em><span class="optional">[</span>, <em>key</em><span class="optional">]</span><big>)</big><a class="headerlink" href="#heapq.nsmallest" title="Permalink to this definition">¶</a></dt>
184
<dd><p>Return a list with the <em>n</em> smallest elements from the dataset defined by
185
<em>iterable</em>. <em>key</em>, if provided, specifies a function of one argument that is
186
used to extract a comparison key from each element in the iterable:
187
<tt class="docutils literal"><span class="pre">key=str.lower</span></tt> Equivalent to: <tt class="docutils literal"><span class="pre">sorted(iterable,</span> <span class="pre">key=key)[:n]</span></tt></p>
188
<div class="versionadded">
189
<p><span class="versionmodified">New in version 2.4.</span></p>
191
<div class="versionchanged">
192
<p><span class="versionmodified">Changed in version 2.5: </span>Added the optional <em>key</em> argument.</p>
196
<p>The latter two functions perform best for smaller values of <em>n</em>. For larger
197
values, it is more efficient to use the <a class="reference internal" href="functions.html#sorted" title="sorted"><tt class="xref py py-func docutils literal"><span class="pre">sorted()</span></tt></a> function. Also, when
198
<tt class="docutils literal"><span class="pre">n==1</span></tt>, it is more efficient to use the built-in <a class="reference internal" href="functions.html#min" title="min"><tt class="xref py py-func docutils literal"><span class="pre">min()</span></tt></a> and <a class="reference internal" href="functions.html#max" title="max"><tt class="xref py py-func docutils literal"><span class="pre">max()</span></tt></a>
199
functions. If repeated usage of these functions is required, consider turning
200
the iterable into an actual heap.</p>
201
<div class="section" id="basic-examples">
202
<h2>8.4.1. Basic Examples<a class="headerlink" href="#basic-examples" title="Permalink to this headline">¶</a></h2>
203
<p>A <a class="reference external" href="http://en.wikipedia.org/wiki/Heapsort">heapsort</a> can be implemented by
204
pushing all values onto a heap and then popping off the smallest values one at a
206
<div class="highlight-python"><div class="highlight"><pre><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>
207
<span class="gp">... </span> <span class="n">h</span> <span class="o">=</span> <span class="p">[]</span>
208
<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>
209
<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>
210
<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>
211
<span class="gp">...</span>
212
<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>
213
<span class="go">[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]</span>
216
<p>This is similar to <tt class="docutils literal"><span class="pre">sorted(iterable)</span></tt>, but unlike <a class="reference internal" href="functions.html#sorted" title="sorted"><tt class="xref py py-func docutils literal"><span class="pre">sorted()</span></tt></a>, this
217
implementation is not stable.</p>
218
<p>Heap elements can be tuples. This is useful for assigning comparison values
219
(such as task priorities) alongside the main record being tracked:</p>
220
<div class="highlight-python"><div class="highlight"><pre><span class="gp">>>> </span><span class="n">h</span> <span class="o">=</span> <span class="p">[]</span>
221
<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="s">'write code'</span><span class="p">))</span>
222
<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="s">'release product'</span><span class="p">))</span>
223
<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="s">'write spec'</span><span class="p">))</span>
224
<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="s">'create tests'</span><span class="p">))</span>
225
<span class="gp">>>> </span><span class="n">heappop</span><span class="p">(</span><span class="n">h</span><span class="p">)</span>
226
<span class="go">(1, 'write spec')</span>
230
<div class="section" id="priority-queue-implementation-notes">
231
<h2>8.4.2. Priority Queue Implementation Notes<a class="headerlink" href="#priority-queue-implementation-notes" title="Permalink to this headline">¶</a></h2>
232
<p>A <a class="reference external" href="http://en.wikipedia.org/wiki/Priority_queue">priority queue</a> is common use
233
for a heap, and it presents several implementation challenges:</p>
235
<li>Sort stability: how do you get two tasks with equal priorities to be returned
236
in the order they were originally added?</li>
237
<li>In the future with Python 3, tuple comparison breaks for (priority, task)
238
pairs if the priorities are equal and the tasks do not have a default
239
comparison order.</li>
240
<li>If the priority of a task changes, how do you move it to a new position in
242
<li>Or if a pending task needs to be deleted, how do you find it and remove it
245
<p>A solution to the first two challenges is to store entries as 3-element list
246
including the priority, an entry count, and the task. The entry count serves as
247
a tie-breaker so that two tasks with the same priority are returned in the order
248
they were added. And since no two entry counts are the same, the tuple
249
comparison will never attempt to directly compare two tasks.</p>
250
<p>The remaining challenges revolve around finding a pending task and making
251
changes to its priority or removing it entirely. Finding a task can be done
252
with a dictionary pointing to an entry in the queue.</p>
253
<p>Removing the entry or changing its priority is more difficult because it would
254
break the heap structure invariants. So, a possible solution is to mark the
255
existing entry as removed and add a new entry with the revised priority:</p>
256
<div class="highlight-python"><div class="highlight"><pre><span class="n">pq</span> <span class="o">=</span> <span class="p">[]</span> <span class="c"># list of entries arranged in a heap</span>
257
<span class="n">entry_finder</span> <span class="o">=</span> <span class="p">{}</span> <span class="c"># mapping of tasks to entries</span>
258
<span class="n">REMOVED</span> <span class="o">=</span> <span class="s">'<removed-task>'</span> <span class="c"># placeholder for a removed task</span>
259
<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="c"># unique sequence count</span>
261
<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>
262
<span class="s">'Add a new task or update the priority of an existing task'</span>
263
<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>
264
<span class="n">remove_task</span><span class="p">(</span><span class="n">task</span><span class="p">)</span>
265
<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>
266
<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>
267
<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>
268
<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>
270
<span class="k">def</span> <span class="nf">remove_task</span><span class="p">(</span><span class="n">task</span><span class="p">):</span>
271
<span class="s">'Mark an existing task as REMOVED. Raise KeyError if not found.'</span>
272
<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>
273
<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>
275
<span class="k">def</span> <span class="nf">pop_task</span><span class="p">():</span>
276
<span class="s">'Remove and return the lowest priority task. Raise KeyError if empty.'</span>
277
<span class="k">while</span> <span class="n">pq</span><span class="p">:</span>
278
<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>
279
<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>
280
<span class="k">del</span> <span class="n">entry_finder</span><span class="p">[</span><span class="n">task</span><span class="p">]</span>
281
<span class="k">return</span> <span class="n">task</span>
282
<span class="k">raise</span> <span class="ne">KeyError</span><span class="p">(</span><span class="s">'pop from an empty priority queue'</span><span class="p">)</span>
286
<div class="section" id="theory">
287
<h2>8.4.3. Theory<a class="headerlink" href="#theory" title="Permalink to this headline">¶</a></h2>
288
<p>Heaps are arrays for which <tt class="docutils literal"><span class="pre">a[k]</span> <span class="pre"><=</span> <span class="pre">a[2*k+1]</span></tt> and <tt class="docutils literal"><span class="pre">a[k]</span> <span class="pre"><=</span> <span class="pre">a[2*k+2]</span></tt> for all
289
<em>k</em>, counting elements from 0. For the sake of comparison, non-existing
290
elements are considered to be infinite. The interesting property of a heap is
291
that <tt class="docutils literal"><span class="pre">a[0]</span></tt> is always its smallest element.</p>
292
<p>The strange invariant above is meant to be an efficient memory representation
293
for a tournament. The numbers below are <em>k</em>, not <tt class="docutils literal"><span class="pre">a[k]</span></tt>:</p>
294
<div class="highlight-python"><div class="highlight"><pre> 0
302
15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
305
<p>In the tree above, each cell <em>k</em> is topping <tt class="docutils literal"><span class="pre">2*k+1</span></tt> and <tt class="docutils literal"><span class="pre">2*k+2</span></tt>. In an usual
306
binary tournament we see in sports, each cell is the winner over the two cells
307
it tops, and we can trace the winner down the tree to see all opponents s/he
308
had. However, in many computer applications of such tournaments, we do not need
309
to trace the history of a winner. To be more memory efficient, when a winner is
310
promoted, we try to replace it by something else at a lower level, and the rule
311
becomes that a cell and the two cells it tops contain three different items, but
312
the top cell “wins” over the two topped cells.</p>
313
<p>If this heap invariant is protected at all time, index 0 is clearly the overall
314
winner. The simplest algorithmic way to remove it and find the “next” winner is
315
to move some loser (let’s say cell 30 in the diagram above) into the 0 position,
316
and then percolate this new 0 down the tree, exchanging values, until the
317
invariant is re-established. This is clearly logarithmic on the total number of
318
items in the tree. By iterating over all items, you get an O(n log n) sort.</p>
319
<p>A nice feature of this sort is that you can efficiently insert new items while
320
the sort is going on, provided that the inserted items are not “better” than the
321
last 0’th element you extracted. This is especially useful in simulation
322
contexts, where the tree holds all incoming events, and the “win” condition
323
means the smallest scheduled time. When an event schedules other events for
324
execution, they are scheduled into the future, so they can easily go into the
325
heap. So, a heap is a good structure for implementing schedulers (this is what
326
I used for my MIDI sequencer :-).</p>
327
<p>Various structures for implementing schedulers have been extensively studied,
328
and heaps are good for this, as they are reasonably speedy, the speed is almost
329
constant, and the worst case is not much different than the average case.
330
However, there are other representations which are more efficient overall, yet
331
the worst cases might be terrible.</p>
332
<p>Heaps are also very useful in big disk sorts. You most probably all know that a
333
big sort implies producing “runs” (which are pre-sorted sequences, whose size is
334
usually related to the amount of CPU memory), followed by a merging passes for
335
these runs, which merging is often very cleverly organised <a class="footnote-reference" href="#id2" id="id1">[1]</a>. It is very
336
important that the initial sort produces the longest runs possible. Tournaments
337
are a good way to achieve that. If, using all the memory available to hold a
338
tournament, you replace and percolate items that happen to fit the current run,
339
you’ll produce runs which are twice the size of the memory for random input, and
340
much better for input fuzzily ordered.</p>
341
<p>Moreover, if you output the 0’th item on disk and get an input which may not fit
342
in the current tournament (because the value “wins” over the last output value),
343
it cannot fit in the heap, so the size of the heap decreases. The freed memory
344
could be cleverly reused immediately for progressively building a second heap,
345
which grows at exactly the same rate the first heap is melting. When the first
346
heap completely vanishes, you switch heaps and start a new run. Clever and
348
<p>In a word, heaps are useful memory structures to know. I use them in a few
349
applications, and I think it is good to keep a ‘heap’ module around. :-)</p>
350
<p class="rubric">Footnotes</p>
351
<table class="docutils footnote" frame="void" id="id2" rules="none">
352
<colgroup><col class="label" /><col /></colgroup>
354
<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
355
than clever, and this is a consequence of the seeking capabilities of the disks.
356
On devices which cannot seek, like big tape drives, the story was quite
357
different, and one had to be very clever to ensure (far in advance) that each
358
tape movement will be the most effective possible (that is, will best
359
participate at “progressing” the merge). Some tapes were even able to read
360
backwards, and this was also used to avoid the rewinding time. Believe me, real
361
good tape sorts were quite spectacular to watch! From all times, sorting has
362
always been a Great Art! :-)</td></tr>
372
<div class="sphinxsidebar">
373
<div class="sphinxsidebarwrapper">
374
<h3><a href="../contents.html">Table Of Contents</a></h3>
376
<li><a class="reference internal" href="#">8.4. <tt class="docutils literal"><span class="pre">heapq</span></tt> — Heap queue algorithm</a><ul>
377
<li><a class="reference internal" href="#basic-examples">8.4.1. Basic Examples</a></li>
378
<li><a class="reference internal" href="#priority-queue-implementation-notes">8.4.2. Priority Queue Implementation Notes</a></li>
379
<li><a class="reference internal" href="#theory">8.4.3. Theory</a></li>
384
<h4>Previous topic</h4>
385
<p class="topless"><a href="collections.html"
386
title="previous chapter">8.3. <tt class="docutils literal"><span class="pre">collections</span></tt> — High-performance container datatypes</a></p>
388
<p class="topless"><a href="bisect.html"
389
title="next chapter">8.5. <tt class="docutils literal"><span class="pre">bisect</span></tt> — Array bisection algorithm</a></p>
391
<ul class="this-page-menu">
392
<li><a href="../bugs.html">Report a Bug</a></li>
393
<li><a href="../_sources/library/heapq.txt"
394
rel="nofollow">Show Source</a></li>
397
<div id="searchbox" style="display: none">
398
<h3>Quick search</h3>
399
<form class="search" action="../search.html" method="get">
400
<input type="text" name="q" />
401
<input type="submit" value="Go" />
402
<input type="hidden" name="check_keywords" value="yes" />
403
<input type="hidden" name="area" value="default" />
405
<p class="searchtip" style="font-size: 90%">
406
Enter search terms or a module, class or function name.
409
<script type="text/javascript">$('#searchbox').show(0);</script>
412
<div class="clearer"></div>
414
<div class="related">
417
<li class="right" style="margin-right: 10px">
418
<a href="../genindex.html" title="General Index"
421
<a href="../py-modindex.html" title="Python Module Index"
424
<a href="bisect.html" title="8.5. bisect — Array bisection algorithm"
427
<a href="collections.html" title="8.3. collections — High-performance container datatypes"
429
<li><img src="../_static/py.png" alt=""
430
style="vertical-align: middle; margin-top: -1px"/></li>
431
<li><a href="https://www.python.org/">Python</a> »</li>
433
<span class="version_switcher_placeholder">2.7.10</span>
434
<a href="../index.html">Documentation</a> »
437
<li><a href="index.html" >The Python Standard Library</a> »</li>
438
<li><a href="datatypes.html" >8. Data Types</a> »</li>
442
© <a href="../copyright.html">Copyright</a> 1990-2015, Python Software Foundation.
444
The Python Software Foundation is a non-profit corporation.
445
<a href="https://www.python.org/psf/donations/">Please donate.</a>
447
Last updated on May 23, 2015.
448
<a href="../bugs.html">Found a bug</a>?
450
Created using <a href="http://sphinx.pocoo.org/">Sphinx</a> 1.2.3.
b'\\ No newline at end of file'