This module provides an implementation of the heap queue algorithm, also known as the priority queue algorithm.

Heaps are arrays for which

and
`heap`[`k`] <= `heap`[2*`k`+1]

for all `heap`[`k`] <= `heap`[2*`k`+2]`k`, 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

is always
its smallest element.
`heap`[0]

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:

is the smallest item, and
`heap`[0]

maintains the heap invariant!
`heap`.sort()

To create a heap, use a list initialized to `[]`

, or you can
transform a populated list into a heap via function `heapify()`.

The following functions are provided:

(`heappush``heap, item`)-
Push the value
`item`onto the`heap`, maintaining the heap invariant.

(`heappop``heap`)-
Pop and return the smallest item from the
`heap`, maintaining the heap invariant. If the heap is empty,`IndexError`is raised.

(`heapify``x`)-
Transform list
`x`into a heap, in-place, in linear time.

(`heapreplace``heap, item`)-
Pop and return the smallest item from the
`heap`, and also push the new`item`. The heap size doesn't change. If the heap is empty,`IndexError`is raised. This is more efficient than`heappop()`followed by`heappush()`, and can be more appropriate when using a fixed-size heap. Note that the value returned may be larger than`item`! That constrains reasonable uses of this routine unless written as part of a conditional replacement:if item > heap[0]: item = heapreplace(heap, item)

Example of use:

>>> from heapq import heappush, heappop >>> heap = [] >>> data = [1, 3, 5, 7, 9, 2, 4, 6, 8, 0] >>> for item in data: ... heappush(heap, item) ... >>> ordered = [] >>> while heap: ... ordered.append(heappop(heap)) ... >>> print ordered [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] >>> data.sort() >>> print data == ordered True >>>

The module also offers two general purpose functions based on heaps.

(`nlargest``n, iterable`[`, key`]`)`-
Return a list with the
`n`largest elements from the dataset defined by`iterable`.`key`, if provided, specifies a function of one argument that is used to extract a comparison key from each element in the iterable: ""Equivalent to: "`key`=`str.lower``sorted(iterable, key=key, reverse=True)[:n]`" New in version 2.4. Changed in version 2.5: Added the optional`key`argument.

(`nsmallest``n, iterable`[`, key`]`)`-
Return a list with the
`n`smallest elements from the dataset defined by`iterable`.`key`, if provided, specifies a function of one argument that is used to extract a comparison key from each element in the iterable: ""Equivalent to: "`key`=`str.lower``sorted(iterable, key=key)[:n]`" New in version 2.4. Changed in version 2.5: Added the optional`key`argument.

Both functions perform best for smaller values of `n`. For larger
values, it is more efficient to use the `sorted()` function. Also,
when `n==1`

, it is more efficient to use the builtin `min()`
and `max()` functions.

See