heap doesn't appear to work as described

7stud bbxx789_05ss at yahoo.com
Tue Apr 3 19:08:14 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.  To test that, I ran
this program:
----------
from heapq import *
from random import shuffle

data = range(10)
shuffle(data)
heap = []
for n in data:
        heappush(heap, n)
print heap

heappush(heap, .5)
print heap

-----output:------
[0, 1, 3, 4, 2, 6, 7, 9, 8, 5]
[0, 0.5, 3, 4, 1, 6, 7, 9, 8, 5, 2]
----------

In the second heap, at position i=2 there is the value 3.  At position
2*i=4, there is the value 1.  3 is not less than 1, which my book
claims should be the case.




More information about the Python-list mailing list