# 5.4 `heapq` -- Heap queue algorithm

New in version 2.3.

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

Heaps are arrays for which `heap[k] <= heap[2*k+1]` and `heap[k] <= heap[2*k+2]` for all 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 `heap[0]` is always its smallest element.

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: `heap[0]` is the smallest item, and `heap.sort()` maintains the heap invariant!

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: "`key=`str.lower``"Equivalent to: "`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: "`key=`str.lower``"Equivalent to: "`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.