| 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"> |
| 56 | 5.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> |
| 66 | This module provides an implementation of the heap queue algorithm, |
| 67 | also known as the priority queue algorithm. |
| 68 | |
| 69 | <P> |
| 70 | Heaps are arrays for which |
| 71 | <code><var>heap</var>[<var>k</var>] <= <var>heap</var>[2*<var>k</var>+1]</code> and |
| 72 | <code><var>heap</var>[<var>k</var>] <= <var>heap</var>[2*<var>k</var>+2]</code> |
| 73 | for all <var>k</var>, counting elements from zero. For the sake of |
| 74 | comparison, non-existing elements are considered to be infinite. The |
| 75 | interesting property of a heap is that <code><var>heap</var>[0]</code> is always |
| 76 | its smallest element. |
| 77 | |
| 78 | <P> |
| 79 | The API below differs from textbook heap algorithms in two aspects: |
| 80 | (a) We use zero-based indexing. This makes the relationship between the |
| 81 | index for a node and the indexes for its children slightly less |
| 82 | obvious, 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 |
| 85 | of its suitability for in-place sorting). |
| 86 | |
| 87 | <P> |
| 88 | These two make it possible to view the heap as a regular Python list |
| 89 | without 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> |
| 93 | To create a heap, use a list initialized to <code>[]</code>, or you can |
| 94 | transform a populated list into a heap via function <tt class="function">heapify()</tt>. |
| 95 | |
| 96 | <P> |
| 97 | The 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> |
| 104 | Push the value <var>item</var> onto the <var>heap</var>, maintaining the |
| 105 | heap 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> |
| 113 | Pop and return the smallest item from the <var>heap</var>, maintaining the |
| 114 | heap 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> |
| 122 | Transform 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> |
| 130 | Pop and return the smallest item from the <var>heap</var>, and also push |
| 131 | the new <var>item</var>. The heap size doesn't change. |
| 132 | If the heap is empty, <tt class="exception">IndexError</tt> is raised. |
| 133 | This is more efficient than <tt class="function">heappop()</tt> followed |
| 134 | by <tt class="function">heappush()</tt>, and can be more appropriate when using |
| 135 | a fixed-size heap. Note that the value returned may be larger |
| 136 | than <var>item</var>! That constrains reasonable uses of this routine |
| 137 | unless written as part of a conditional replacement: |
| 138 | <div class="verbatim"><pre> |
| 139 | if item > heap[0]: |
| 140 | item = heapreplace(heap, item) |
| 141 | </pre></div> |
| 142 | </dl> |
| 143 | |
| 144 | <P> |
| 145 | Example of use: |
| 146 | |
| 147 | <P> |
| 148 | <div class="verbatim"><pre> |
| 149 | >>> from heapq import heappush, heappop |
| 150 | >>> heap = [] |
| 151 | >>> data = [1, 3, 5, 7, 9, 2, 4, 6, 8, 0] |
| 152 | >>> for item in data: |
| 153 | ... heappush(heap, item) |
| 154 | ... |
| 155 | >>> sorted = [] |
| 156 | >>> while heap: |
| 157 | ... sorted.append(heappop(heap)) |
| 158 | ... |
| 159 | >>> print sorted |
| 160 | [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] |
| 161 | >>> data.sort() |
| 162 | >>> print data == sorted |
| 163 | True |
| 164 | >>> |
| 165 | </pre></div> |
| 166 | |
| 167 | <P> |
| 168 | The 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> |
| 175 | Return a list with the <var>n</var> largest elements from the dataset defined |
| 176 | by <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> |
| 187 | Return a list with the <var>n</var> smallest elements from the dataset defined |
| 188 | by <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> |
| 195 | Both functions perform best for smaller values of <var>n</var>. For larger |
| 196 | values, it is more efficient to use the <tt class="function">sorted()</tt> function. Also, |
| 197 | when <code>n==1</code>, it is more efficient to use the builtin <tt class="function">min()</tt> |
| 198 | and <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> |
| 251 | See <i><a href="about.html">About this document...</a></i> for information on suggesting changes. |
| 252 | </ADDRESS> |
| 253 | </BODY> |
| 254 | </HTML> |