heap doesn't appear to work as described

[skip at pobox.com]

    >> My book says that in a heap, a value at position i will be smaller
    >> than the values at positions 2*i and 2*i + 1.  

Check the heapq docs for the constraints the Python heapq module maintains:

    http://docs.python.org/dev/lib/module-heapq.html

They are different than what you stated above:

    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.

Skip