# The heapq Module

(New in 2.3) This module provides functions to add and remove items from partially sorted sequences.

The functions in this module all assume that the sequence is sorted so
that the first item in the sequence (*seq[0]*) is the smallest, and
that the rest of the sequence forms a binary tree, where the children
of *seq[i]* are *seq[2*i+1]* and *seq[2*i+2]*. When
modifying the sequence, the functions always make sure that the children
are equal to or larger than their parent.

Given an empty sequence, you can use **heappush** to add items to
the sequence, and **heappop** to remove the smallest item from the
sequence.

# File: heapq-example-1.py import heapq heap = [] # add some values to the heap for value in [20, 10, 30, 50, 40]: heapq.heappush(heap, value) # pop them off, in order while heap: print heapq.heappop(heap),

$ python heapq-example-1.py 10 20 30 40 50

(This is a lot more efficient than using **min** to get the
smallest item, and the **remove** and **append** methods to
modify the sequence.)

If you have an existing sequence, you can use the **heapify**
function to turn it into a well-formed heap:

# File: heapq-example-2.py import heapq heap = [20, 10, 30, 50, 40] heapq.heapify(heap) # pop them off, in order while heap: print heapq.heappop(heap),

$ python heapq-example-2.py 10 20 30 40 50

Note that if you have a sorted list, you don’t really have to call
the **heapify** function; a sorted list is a valid heap tree. Also
note that an empty list and a list with only one item both qualify as
“sorted”.

The **heapq** module can be used to implement various kind of priority
queues and schedulers (where the item value represents a process priority
or a timestamp).