# phpman > pydoc > _heapq

Help on built-in module _heapq:

## NAME
    _heapq - Heap queue algorithm (a.k.a. priority queue).

## DESCRIPTION
    Heaps are arrays for which a[k] <= a[2*k+1] and a[k] <= a[2*k+2] for
    all k, counting elements from 0.  For the sake of comparison,
    non-existing elements are considered to be infinite.  The interesting
    property of a heap is that a[0] is always its smallest element.

    Usage:

    heap = []            # creates an empty heap
### heappush
    item = heappop(heap) # pops the smallest item from the heap
    item = heap[0]       # smallest item on the heap without popping it
### heapify
    item = heapreplace(heap, item) # pops and returns smallest item, and adds
                                   # new item; the heap size is unchanged

    Our API differs from textbook heap algorithms as follows:

    - We use 0-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 0-based indexing.

    - Our heappop() method returns the smallest item, not the largest.

    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!

## FUNCTIONS
### heapify
        Transform list into a heap, in-place, in O(len(heap)) time.

### heappop
        Pop the smallest item off the heap, maintaining the heap invariant.

### heappush
        Push item onto heap, maintaining the heap invariant.

### heappushpop
        Push item on the heap, then pop and return the smallest item from the heap.

        The combined action runs more efficiently than heappush() followed by
        a separate call to heappop().

### heapreplace
        Pop and return the current smallest value, and add the new item.

        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)

## DATA
    __about__ = 'Heap queues\n\n[explanation by François Pinard]\n\nH... t...

## FILE
    (built-in)