heap doesn't appear to work as described

skip at pobox.com skip at pobox.com
Tue Apr 3 19:27:30 EDT 2007


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



More information about the Python-list mailing list