<!DOCTYPE html PUBLIC
"-//W3C//DTD HTML 4.0 Transitional//EN">
<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>
<div id='top-navigation-panel' xml:id='top-navigation-panel'
>
<table align=
"center" width=
"100%" cellpadding=
"0" cellspacing=
"2">
<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><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>
<!--End of Navigation Panel-->
<H1><A NAME=
"SECTION0071300000000000000000">
5.13 <tt class=
"module">heapq
</tt> --
<A NAME=
"module-heapq"></A>
<span class=
"versionnote">New in version
2.3.
</span>
This module provides an implementation of the heap queue algorithm,
also known as the priority queue algorithm.
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
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).
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!
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>.
The following functions are provided:
<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>
Push the value
<var>item
</var> onto the
<var>heap
</var>, maintaining the
<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>
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><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>
Transform list
<var>x
</var> into a heap, in-place, in linear time.
<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>
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>
item = heapreplace(heap, item)
<div class=
"verbatim"><pre>
>>> from heapq import heappush, heappop
>>> data = [
1,
3,
5,
7,
9,
2,
4,
6,
8,
0]
>>> for item in data:
... sorted.append(heappop(heap))
>>> print sorted
[
0,
1,
2,
3,
4,
5,
6,
7,
8,
9]
>>> print data == sorted
The module also offers two general purpose functions based on heaps.
<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>
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><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>
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>
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><br /></p><hr class='online-navigation'
/>
<div class='online-navigation'
>
<!--Table of Child-Links-->
<A NAME=
"CHILD_LINKS"><STRONG>Subsections
</STRONG></a>
<LI><A href=
"node196.html">5.13.1 Theory
</a>
<!--End of Table of Child-Links-->
<div class='online-navigation'
>
<table align=
"center" width=
"100%" cellpadding=
"0" cellspacing=
"2">
<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><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>
<span class=
"release-info">Release
2.4.2, documentation updated on
28 September
2005.
</span>
<!--End of Navigation Panel-->
See
<i><a href=
"about.html">About this document...
</a></i> for information on suggesting changes.
projects / OpenSPARC-T2-SAM / blob