projects / OpenSPARC-T2-DV / blame
? search:
summary | tags | clone url | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
Initial commit of OpenSPARC T2 design and verification files.
[OpenSPARC-T2-DV] / tools / src / nas,5.n2.os.2 / lib / python / html / python / lib / module-heapq.html
CommitLineData
86530b38
AT		 1<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
2<html>
3<head>
4<link rel="STYLESHEET" href="lib.css" type='text/css' />
5<link rel="SHORTCUT ICON" href="../icons/pyfav.png" type="image/png" />
6<link rel='start' href='../index.html' title='Python Documentation Index' />
7<link rel="first" href="lib.html" title='Python Library Reference' />
8<link rel='contents' href='contents.html' title="Contents" />
9<link rel='index' href='genindex.html' title='Index' />
10<link rel='last' href='about.html' title='About this document...' />
11<link rel='help' href='about.html' title='About this document...' />
12<link rel="next" href="module-array.html" />
13<link rel="prev" href="module-collections.html" />
14<link rel="parent" href="misc.html" />
15<link rel="next" href="node196.html" />
16<meta name='aesop' content='information' />
17<title>5.13 heapq -- Heap queue algorithm</title>
18</head>
19<body>
20<DIV CLASS="navigation">
21<div id='top-navigation-panel' xml:id='top-navigation-panel'>
22<table align="center" width="100%" cellpadding="0" cellspacing="2">
23<tr>
24<td class='online-navigation'><a rel="prev" title="5.12.1 Recipes"
25 href="deque-recipes.html"><img src='../icons/previous.png'
26 border='0' height='32' alt='Previous Page' width='32' /></A></td>
27<td class='online-navigation'><a rel="parent" title="5. Miscellaneous Services"
28 href="misc.html"><img src='../icons/up.png'
29 border='0' height='32' alt='Up One Level' width='32' /></A></td>
30<td class='online-navigation'><a rel="next" title="5.13.1 Theory"
31 href="node196.html"><img src='../icons/next.png'
32 border='0' height='32' alt='Next Page' width='32' /></A></td>
33<td align="center" width="100%">Python Library Reference</td>
34<td class='online-navigation'><a rel="contents" title="Table of Contents"
35 href="contents.html"><img src='../icons/contents.png'
36 border='0' height='32' alt='Contents' width='32' /></A></td>
37<td class='online-navigation'><a href="modindex.html" title="Module Index"><img src='../icons/modules.png'
38 border='0' height='32' alt='Module Index' width='32' /></a></td>
39<td class='online-navigation'><a rel="index" title="Index"
40 href="genindex.html"><img src='../icons/index.png'
41 border='0' height='32' alt='Index' width='32' /></A></td>
42</tr></table>
43<div class='online-navigation'>
44<b class="navlabel">Previous:</b>
45<a class="sectref" rel="prev" href="deque-recipes.html">5.12.1 Recipes</A>
46<b class="navlabel">Up:</b>
47<a class="sectref" rel="parent" href="misc.html">5. Miscellaneous Services</A>
48<b class="navlabel">Next:</b>
49<a class="sectref" rel="next" href="node196.html">5.13.1 Theory</A>
50</div>
51<hr /></div>
52</DIV>
53<!--End of Navigation Panel-->
54
55<H1><A NAME="SECTION0071300000000000000000">
565.13 <tt class="module">heapq</tt> --
57 Heap queue algorithm</A>
58</H1>
59
60<P>
61<A NAME="module-heapq"></A>
62
63<span class="versionnote">New in version 2.3.</span>
64
65<P>
66This module provides an implementation of the heap queue algorithm,
67also known as the priority queue algorithm.
68
69<P>
70Heaps are arrays for which
71<code><var>heap</var>[<var>k</var>] &lt;= <var>heap</var>[2*<var>k</var>+1]</code> and
72<code><var>heap</var>[<var>k</var>] &lt;= <var>heap</var>[2*<var>k</var>+2]</code>
73for all <var>k</var>, counting elements from zero. For the sake of
74comparison, non-existing elements are considered to be infinite. The
75interesting property of a heap is that <code><var>heap</var>[0]</code> is always
76its smallest element.
77
78<P>
79The API below differs from textbook heap algorithms in two aspects:
80(a) We use zero-based indexing. This makes the relationship between the
81index for a node and the indexes for its children slightly less
82obvious, but is more suitable since Python uses zero-based indexing.
83(b) Our pop method returns the smallest item, not the largest (called a
84"min heap" in textbooks; a "max heap" is more common in texts because
85of its suitability for in-place sorting).
86
87<P>
88These two make it possible to view the heap as a regular Python list
89without surprises: <code><var>heap</var>[0]</code> is the smallest item, and
90<code><var>heap</var>.sort()</code> maintains the heap invariant!
91
92<P>
93To create a heap, use a list initialized to <code>[]</code>, or you can
94transform a populated list into a heap via function <tt class="function">heapify()</tt>.
95
96<P>
97The following functions are provided:
98
99<P>
100<dl><dt><table cellpadding="0" cellspacing="0"><tr valign="baseline">
101 <td><nobr><b><tt id='l2h-1347' xml:id='l2h-1347' class="function">heappush</tt></b>(</nobr></td>
102 <td><var>heap, item</var>)</td></tr></table></dt>
103<dd>
104Push the value <var>item</var> onto the <var>heap</var>, maintaining the
105heap invariant.
106</dl>
107
108<P>
109<dl><dt><table cellpadding="0" cellspacing="0"><tr valign="baseline">
110 <td><nobr><b><tt id='l2h-1348' xml:id='l2h-1348' class="function">heappop</tt></b>(</nobr></td>
111 <td><var>heap</var>)</td></tr></table></dt>
112<dd>
113Pop and return the smallest item from the <var>heap</var>, maintaining the
114heap invariant. If the heap is empty, <tt class="exception">IndexError</tt> is raised.
115</dl>
116
117<P>
118<dl><dt><table cellpadding="0" cellspacing="0"><tr valign="baseline">
119 <td><nobr><b><tt id='l2h-1349' xml:id='l2h-1349' class="function">heapify</tt></b>(</nobr></td>
120 <td><var>x</var>)</td></tr></table></dt>
121<dd>
122Transform list <var>x</var> into a heap, in-place, in linear time.
123</dl>
124
125<P>
126<dl><dt><table cellpadding="0" cellspacing="0"><tr valign="baseline">
127 <td><nobr><b><tt id='l2h-1350' xml:id='l2h-1350' class="function">heapreplace</tt></b>(</nobr></td>
128 <td><var>heap, item</var>)</td></tr></table></dt>
129<dd>
130Pop and return the smallest item from the <var>heap</var>, and also push
131the new <var>item</var>. The heap size doesn't change.
132If the heap is empty, <tt class="exception">IndexError</tt> is raised.
133This is more efficient than <tt class="function">heappop()</tt> followed
134by <tt class="function">heappush()</tt>, and can be more appropriate when using
135a fixed-size heap. Note that the value returned may be larger
136than <var>item</var>! That constrains reasonable uses of this routine
137unless written as part of a conditional replacement:
138<div class="verbatim"><pre>
139 if item &gt; heap[0]:
140 item = heapreplace(heap, item)
141</pre></div>
142</dl>
143
144<P>
145Example of use:
146
147<P>
148<div class="verbatim"><pre>
149&gt;&gt;&gt; from heapq import heappush, heappop
150&gt;&gt;&gt; heap = []
151&gt;&gt;&gt; data = [1, 3, 5, 7, 9, 2, 4, 6, 8, 0]
152&gt;&gt;&gt; for item in data:
153... heappush(heap, item)
154...
155&gt;&gt;&gt; sorted = []
156&gt;&gt;&gt; while heap:
157... sorted.append(heappop(heap))
158...
159&gt;&gt;&gt; print sorted
160[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
161&gt;&gt;&gt; data.sort()
162&gt;&gt;&gt; print data == sorted
163True
164&gt;&gt;&gt;
165</pre></div>
166
167<P>
168The module also offers two general purpose functions based on heaps.
169
170<P>
171<dl><dt><table cellpadding="0" cellspacing="0"><tr valign="baseline">
172 <td><nobr><b><tt id='l2h-1351' xml:id='l2h-1351' class="function">nlargest</tt></b>(</nobr></td>
173 <td><var>n, iterable</var>)</td></tr></table></dt>
174<dd>
175Return a list with the <var>n</var> largest elements from the dataset defined
176by <var>iterable</var>. Equivalent to: <code>sorted(iterable, reverse=True)[:n]</code>
177
178<span class="versionnote">New in version 2.4.</span>
179
180</dl>
181
182<P>
183<dl><dt><table cellpadding="0" cellspacing="0"><tr valign="baseline">
184 <td><nobr><b><tt id='l2h-1352' xml:id='l2h-1352' class="function">nsmallest</tt></b>(</nobr></td>
185 <td><var>n, iterable</var>)</td></tr></table></dt>
186<dd>
187Return a list with the <var>n</var> smallest elements from the dataset defined
188by <var>iterable</var>. Equivalent to: <code>sorted(iterable)[:n]</code>
189
190<span class="versionnote">New in version 2.4.</span>
191
192</dl>
193
194<P>
195Both functions perform best for smaller values of <var>n</var>. For larger
196values, it is more efficient to use the <tt class="function">sorted()</tt> function. Also,
197when <code>n==1</code>, it is more efficient to use the builtin <tt class="function">min()</tt>
198and <tt class="function">max()</tt> functions.
199
200<P>
201
202<p><br /></p><hr class='online-navigation' />
203<div class='online-navigation'>
204<!--Table of Child-Links-->
205<A NAME="CHILD_LINKS"><STRONG>Subsections</STRONG></a>
206
207<UL CLASS="ChildLinks">
208<LI><A href="node196.html">5.13.1 Theory</a>
209</ul>
210<!--End of Table of Child-Links-->
211</div>
212
213<DIV CLASS="navigation">
214<div class='online-navigation'>
215<p></p><hr />
216<table align="center" width="100%" cellpadding="0" cellspacing="2">
217<tr>
218<td class='online-navigation'><a rel="prev" title="5.12.1 Recipes"
219 href="deque-recipes.html"><img src='../icons/previous.png'
220 border='0' height='32' alt='Previous Page' width='32' /></A></td>
221<td class='online-navigation'><a rel="parent" title="5. Miscellaneous Services"
222 href="misc.html"><img src='../icons/up.png'
223 border='0' height='32' alt='Up One Level' width='32' /></A></td>
224<td class='online-navigation'><a rel="next" title="5.13.1 Theory"
225 href="node196.html"><img src='../icons/next.png'
226 border='0' height='32' alt='Next Page' width='32' /></A></td>
227<td align="center" width="100%">Python Library Reference</td>
228<td class='online-navigation'><a rel="contents" title="Table of Contents"
229 href="contents.html"><img src='../icons/contents.png'
230 border='0' height='32' alt='Contents' width='32' /></A></td>
231<td class='online-navigation'><a href="modindex.html" title="Module Index"><img src='../icons/modules.png'
232 border='0' height='32' alt='Module Index' width='32' /></a></td>
233<td class='online-navigation'><a rel="index" title="Index"
234 href="genindex.html"><img src='../icons/index.png'
235 border='0' height='32' alt='Index' width='32' /></A></td>
236</tr></table>
237<div class='online-navigation'>
238<b class="navlabel">Previous:</b>
239<a class="sectref" rel="prev" href="deque-recipes.html">5.12.1 Recipes</A>
240<b class="navlabel">Up:</b>
241<a class="sectref" rel="parent" href="misc.html">5. Miscellaneous Services</A>
242<b class="navlabel">Next:</b>
243<a class="sectref" rel="next" href="node196.html">5.13.1 Theory</A>
244</div>
245</div>
246<hr />
247<span class="release-info">Release 2.4.2, documentation updated on 28 September 2005.</span>
248</DIV>
249<!--End of Navigation Panel-->
250<ADDRESS>
251See <i><a href="about.html">About this document...</a></i> for information on suggesting changes.
252</ADDRESS>
253</BODY>
254</HTML>
Full OpenSPARC design & verification tarball including full HDL.