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.

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) ... >>> 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 >>>

See