=====================================
heapq -- In-place heap sort algorithm
=====================================
.. module:: heapq
:synopsis: In-place heap sort algorithm
:Purpose:
The heapq implements a min-heap sort algorithm suitable for use with
Python's lists.
:Python Version: New in 2.3 with additions in 2.5
A *heap* is a tree-like data structure where the child nodes have a
sort-order relationship with the parents. *Binary heaps* can be
represented using a list or array organized so that the children of
element N are at positions 2*N+1 and 2*N+2 (for zero-based
indexes). This layout makes it possible to rearrange heaps in place,
so it is not necessary to reallocate as much memory when adding or
removing items.
A max-heap ensures that the parent is larger than or equal to both of
its children. A min-heap requires that the parent be less than or
equal to its children. Python's heapq module implements a min-heap.
Example Data
============
The examples below use this sample data:
.. include:: heapq_heapdata.py
:literal:
:start-after: #end_pymotw_header
The heap output is printed using ``heapq_showtree.py``:
.. include:: heapq_showtree.py
:literal:
:start-after: #end_pymotw_header
Creating a Heap
===============
There are 2 basic ways to create a heap, ``heappush()`` and
``heapify()``.
Using ``heappush()``, the heap sort order of the elements is
maintained as new items are added from a data source.
.. include:: heapq_heappush.py
:literal:
:start-after: #end_pymotw_header
.. {{{cog
.. cog.out(run_script(cog.inFile, 'heapq_heappush.py'))
.. }}}
::
$ python heapq_heappush.py
random : [19, 9, 4, 10, 11, 8, 2]
add 19:
19
------------------------------------
add 9:
9
19
------------------------------------
add 4:
4
19 9
------------------------------------
add 10:
4
10 9
19
------------------------------------
add 11:
4
10 9
19 11
------------------------------------
add 8:
4
10 8
19 11 9
------------------------------------
add 2:
2
10 4
19 11 9 8
------------------------------------
.. {{{end}}}
If the data is already in memory, it is more efficient to use
``heapify()`` to rearrange the items of the list in place.
.. include:: heapq_heapify.py
:literal:
:start-after: #end_pymotw_header
.. {{{cog
.. cog.out(run_script(cog.inFile, 'heapq_heapify.py'))
.. }}}
::
$ python heapq_heapify.py
random : [19, 9, 4, 10, 11, 8, 2]
heapified :
2
9 4
10 11 8 19
------------------------------------
.. {{{end}}}
Accessing Contents of a Heap
============================
Once the heap is organized correctly, use ``heappop()`` to remove the
element with the lowest value. In this example, adapted from the
stdlib documentation, ``heapify()`` and ``heappop()`` are used to sort
a list of numbers.
.. include:: heapq_heappop.py
:literal:
:start-after: #end_pymotw_header
.. {{{cog
.. cog.out(run_script(cog.inFile, 'heapq_heappop.py'))
.. }}}
::
$ python heapq_heappop.py
random : [19, 9, 4, 10, 11, 8, 2]
heapified :
2
9 4
10 11 8 19
------------------------------------
pop 2:
4
9 8
10 11 19
------------------------------------
pop 4:
8
9 19
10 11
------------------------------------
pop 8:
9
10 19
11
------------------------------------
pop 9:
10
11 19
------------------------------------
pop 10:
11
19
------------------------------------
pop 11:
19
------------------------------------
pop 19:
------------------------------------
inorder : [2, 4, 8, 9, 10, 11, 19]
.. {{{end}}}
To remove existing elements and replace them with new values in a
single operation, use ``heapreplace()``.
.. include:: heapq_heapreplace.py
:literal:
:start-after: #end_pymotw_header
Replacing elements in place lets you maintain a fixed size heap, such
as a queue of jobs ordered by priority.
.. {{{cog
.. cog.out(run_script(cog.inFile, 'heapq_heapreplace.py'))
.. }}}
::
$ python heapq_heapreplace.py
start:
2
9 4
10 11 8 19
------------------------------------
replace 2 with 0:
0
9 4
10 11 8 19
------------------------------------
replace 0 with 7:
4
9 7
10 11 8 19
------------------------------------
replace 4 with 13:
7
9 8
10 11 13 19
------------------------------------
replace 7 with 9:
8
9 9
10 11 13 19
------------------------------------
replace 8 with 5:
5
9 9
10 11 13 19
------------------------------------
.. {{{end}}}
Data Extremes
=============
:mod:`heapq` also includes 2 functions to examine an iterable to find
a range of the largest or smallest values it contains. Using
``nlargest()`` and ``nsmallest()`` are really only efficient for
relatively small values of n > 1, but can still come in handy in a few
cases.
.. include:: heapq_extremes.py
:literal:
:start-after: #end_pymotw_header
.. {{{cog
.. cog.out(run_script(cog.inFile, 'heapq_extremes.py'))
.. }}}
::
$ python heapq_extremes.py
all : [19, 9, 4, 10, 11, 8, 2]
3 largest : [19, 11, 10]
from sort : [19, 11, 10]
3 smallest: [2, 4, 8]
from sort : [2, 4, 8]
.. {{{end}}}
.. seealso::
`heapq <http://docs.python.org/library/heapq.html>`_
The standard library documentation for this module.
`WikiPedia: Heap (data structure) <http://en.wikipedia.org/wiki/Heap_(data_structure)>`_
A general description of heap data structures.
:ref:`article-data-structures`
Other Python data structures.
:ref:`Queue-PriorityQueue`
A priority queue implementation from :mod:`Queue` in the
standard library.