File: //usr/share/doc/python-docs-2.4.3/html/lib/module-heapq.html
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<html>
<head>
<link rel="STYLESHEET" href="lib.css" type='text/css' />
<link rel="SHORTCUT ICON" href="../icons/pyfav.png" type="image/png" />
<link rel='start' href='../index.html' title='Python Documentation Index' />
<link rel="first" href="lib.html" title='Python Library Reference' />
<link rel='contents' href='contents.html' title="Contents" />
<link rel='index' href='genindex.html' title='Index' />
<link rel='last' href='about.html' title='About this document...' />
<link rel='help' href='about.html' title='About this document...' />
<link rel="next" href="module-array.html" />
<link rel="prev" href="module-collections.html" />
<link rel="parent" href="misc.html" />
<link rel="next" href="node196.html" />
<meta name='aesop' content='information' />
<title>5.13 heapq -- Heap queue algorithm</title>
</head>
<body>
<DIV CLASS="navigation">
<div id='top-navigation-panel' xml:id='top-navigation-panel'>
<table align="center" width="100%" cellpadding="0" cellspacing="2">
<tr>
<td class='online-navigation'><a rel="prev" title="5.12.1 Recipes"
href="deque-recipes.html"><img src='../icons/previous.png'
border='0' height='32' alt='Previous Page' width='32' /></A></td>
<td class='online-navigation'><a rel="parent" title="5. Miscellaneous Services"
href="misc.html"><img src='../icons/up.png'
border='0' height='32' alt='Up One Level' width='32' /></A></td>
<td class='online-navigation'><a rel="next" title="5.13.1 Theory"
href="node196.html"><img src='../icons/next.png'
border='0' height='32' alt='Next Page' width='32' /></A></td>
<td align="center" width="100%">Python Library Reference</td>
<td class='online-navigation'><a rel="contents" title="Table of Contents"
href="contents.html"><img src='../icons/contents.png'
border='0' height='32' alt='Contents' width='32' /></A></td>
<td class='online-navigation'><a href="modindex.html" title="Module Index"><img src='../icons/modules.png'
border='0' height='32' alt='Module Index' width='32' /></a></td>
<td class='online-navigation'><a rel="index" title="Index"
href="genindex.html"><img src='../icons/index.png'
border='0' height='32' alt='Index' width='32' /></A></td>
</tr></table>
<div class='online-navigation'>
<b class="navlabel">Previous:</b>
<a class="sectref" rel="prev" href="deque-recipes.html">5.12.1 Recipes</A>
<b class="navlabel">Up:</b>
<a class="sectref" rel="parent" href="misc.html">5. Miscellaneous Services</A>
<b class="navlabel">Next:</b>
<a class="sectref" rel="next" href="node196.html">5.13.1 Theory</A>
</div>
<hr /></div>
</DIV>
<!--End of Navigation Panel-->
<H1><A NAME="SECTION0071300000000000000000">
5.13 <tt class="module">heapq</tt> --
Heap queue algorithm</A>
</H1>
<P>
<A NAME="module-heapq"></A>
<span class="versionnote">New in version 2.3.</span>
<P>
This module provides an implementation of the heap queue algorithm,
also known as the priority queue algorithm.
<P>
Heaps are arrays for which
<code><var>heap</var>[<var>k</var>] <= <var>heap</var>[2*<var>k</var>+1]</code> and
<code><var>heap</var>[<var>k</var>] <= <var>heap</var>[2*<var>k</var>+2]</code>
for all <var>k</var>, 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 <code><var>heap</var>[0]</code> is always
its smallest element.
<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>
These two make it possible to view the heap as a regular Python list
without surprises: <code><var>heap</var>[0]</code> is the smallest item, and
<code><var>heap</var>.sort()</code> maintains the heap invariant!
<P>
To create a heap, use a list initialized to <code>[]</code>, or you can
transform a populated list into a heap via function <tt class="function">heapify()</tt>.
<P>
The following functions are provided:
<P>
<dl><dt><table cellpadding="0" cellspacing="0"><tr valign="baseline">
<td><nobr><b><tt id='l2h-1347' xml:id='l2h-1347' class="function">heappush</tt></b>(</nobr></td>
<td><var>heap, item</var>)</td></tr></table></dt>
<dd>
Push the value <var>item</var> onto the <var>heap</var>, maintaining the
heap invariant.
</dl>
<P>
<dl><dt><table cellpadding="0" cellspacing="0"><tr valign="baseline">
<td><nobr><b><tt id='l2h-1348' xml:id='l2h-1348' class="function">heappop</tt></b>(</nobr></td>
<td><var>heap</var>)</td></tr></table></dt>
<dd>
Pop and return the smallest item from the <var>heap</var>, maintaining the
heap invariant. If the heap is empty, <tt class="exception">IndexError</tt> is raised.
</dl>
<P>
<dl><dt><table cellpadding="0" cellspacing="0"><tr valign="baseline">
<td><nobr><b><tt id='l2h-1349' xml:id='l2h-1349' class="function">heapify</tt></b>(</nobr></td>
<td><var>x</var>)</td></tr></table></dt>
<dd>
Transform list <var>x</var> into a heap, in-place, in linear time.
</dl>
<P>
<dl><dt><table cellpadding="0" cellspacing="0"><tr valign="baseline">
<td><nobr><b><tt id='l2h-1350' xml:id='l2h-1350' class="function">heapreplace</tt></b>(</nobr></td>
<td><var>heap, item</var>)</td></tr></table></dt>
<dd>
Pop and return the smallest item from the <var>heap</var>, and also push
the new <var>item</var>. The heap size doesn't change.
If the heap is empty, <tt class="exception">IndexError</tt> is raised.
This is more efficient than <tt class="function">heappop()</tt> followed
by <tt class="function">heappush()</tt>, and can be more appropriate when using
a fixed-size heap. Note that the value returned may be larger
than <var>item</var>! That constrains reasonable uses of this routine
unless written as part of a conditional replacement:
<div class="verbatim"><pre>
if item > heap[0]:
item = heapreplace(heap, item)
</pre></div>
</dl>
<P>
Example of use:
<P>
<div class="verbatim"><pre>
>>> from heapq import heappush, heappop
>>> heap = []
>>> data = [1, 3, 5, 7, 9, 2, 4, 6, 8, 0]
>>> for item in data:
... heappush(heap, item)
...
>>> sorted = []
>>> while heap:
... sorted.append(heappop(heap))
...
>>> print sorted
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> data.sort()
>>> print data == sorted
True
>>>
</pre></div>
<P>
The module also offers two general purpose functions based on heaps.
<P>
<dl><dt><table cellpadding="0" cellspacing="0"><tr valign="baseline">
<td><nobr><b><tt id='l2h-1351' xml:id='l2h-1351' class="function">nlargest</tt></b>(</nobr></td>
<td><var>n, iterable</var>)</td></tr></table></dt>
<dd>
Return a list with the <var>n</var> largest elements from the dataset defined
by <var>iterable</var>. Equivalent to: <code>sorted(iterable, reverse=True)[:n]</code>
<span class="versionnote">New in version 2.4.</span>
</dl>
<P>
<dl><dt><table cellpadding="0" cellspacing="0"><tr valign="baseline">
<td><nobr><b><tt id='l2h-1352' xml:id='l2h-1352' class="function">nsmallest</tt></b>(</nobr></td>
<td><var>n, iterable</var>)</td></tr></table></dt>
<dd>
Return a list with the <var>n</var> smallest elements from the dataset defined
by <var>iterable</var>. Equivalent to: <code>sorted(iterable)[:n]</code>
<span class="versionnote">New in version 2.4.</span>
</dl>
<P>
Both functions perform best for smaller values of <var>n</var>. For larger
values, it is more efficient to use the <tt class="function">sorted()</tt> function. Also,
when <code>n==1</code>, it is more efficient to use the builtin <tt class="function">min()</tt>
and <tt class="function">max()</tt> functions.
<P>
<p><br /></p><hr class='online-navigation' />
<div class='online-navigation'>
<!--Table of Child-Links-->
<A NAME="CHILD_LINKS"><STRONG>Subsections</STRONG></a>
<UL CLASS="ChildLinks">
<LI><A href="node196.html">5.13.1 Theory</a>
</ul>
<!--End of Table of Child-Links-->
</div>
<DIV CLASS="navigation">
<div class='online-navigation'>
<p></p><hr />
<table align="center" width="100%" cellpadding="0" cellspacing="2">
<tr>
<td class='online-navigation'><a rel="prev" title="5.12.1 Recipes"
href="deque-recipes.html"><img src='../icons/previous.png'
border='0' height='32' alt='Previous Page' width='32' /></A></td>
<td class='online-navigation'><a rel="parent" title="5. Miscellaneous Services"
href="misc.html"><img src='../icons/up.png'
border='0' height='32' alt='Up One Level' width='32' /></A></td>
<td class='online-navigation'><a rel="next" title="5.13.1 Theory"
href="node196.html"><img src='../icons/next.png'
border='0' height='32' alt='Next Page' width='32' /></A></td>
<td align="center" width="100%">Python Library Reference</td>
<td class='online-navigation'><a rel="contents" title="Table of Contents"
href="contents.html"><img src='../icons/contents.png'
border='0' height='32' alt='Contents' width='32' /></A></td>
<td class='online-navigation'><a href="modindex.html" title="Module Index"><img src='../icons/modules.png'
border='0' height='32' alt='Module Index' width='32' /></a></td>
<td class='online-navigation'><a rel="index" title="Index"
href="genindex.html"><img src='../icons/index.png'
border='0' height='32' alt='Index' width='32' /></A></td>
</tr></table>
<div class='online-navigation'>
<b class="navlabel">Previous:</b>
<a class="sectref" rel="prev" href="deque-recipes.html">5.12.1 Recipes</A>
<b class="navlabel">Up:</b>
<a class="sectref" rel="parent" href="misc.html">5. Miscellaneous Services</A>
<b class="navlabel">Next:</b>
<a class="sectref" rel="next" href="node196.html">5.13.1 Theory</A>
</div>
</div>
<hr />
<span class="release-info">Release 2.4.3, documentation updated on 29 March 2006.</span>
</DIV>
<!--End of Navigation Panel-->
<ADDRESS>
See <i><a href="about.html">About this document...</a></i> for information on suggesting changes.
</ADDRESS>
</BODY>
</HTML>