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

### Like this:

Like Loading...

*Related*