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

 

A Django site. rendered by a django application. hosted by webfaction.