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 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
heap 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:
if item > heap: 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) ... >>> 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 >>>
The module also offers two general purpose functions based on heaps.
sorted(iterable, reverse=True)[:n]New in version 2.4.
sorted(iterable)[:n]New in version 2.4.
Both functions perform best for smaller values of n. For larger
values, it is more efficient to use the sorted() function. Also,
n==1, it is more efficient to use the builtin min()
and max() functions.