--- Neil Cerutti <horp@yahoo.com> wrote:

Heapq will perform much better for a large enough data
set, if the only thing that you eventually want to do
is occasionally pop off the first item or items in the
list.  One could even argue that it's a pretty rare
situation that you go through the trouble of keeping a
list sorted, only to occasionally randomly access the
data.

One more caveat--apart from the more constrained
semantics, heaps have the disadvantage of actually
being slower for a small enough dataset.  I haven't
measured this particular scenario, but any complicated
data structure usually loses out to a simple data
structure for small data sets, but as you get larger
and larger data sets, the more sophisticated data
structure begins to have big wins.

A typical use of heapq is for keeping a priority
queue.  See sched.py in the standard library for a
pretty simple and well commented example.