heap doesn't appear to work as described

[Terry Reedy]

<skip at pobox.com> wrote in message 
news:17938.58082.317522.331513 at montanaro.dyndns.org...
|
|    >> 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.

I am sure your book either uses 1-based arrays or a 0-based arrays with the 
first not used.  The need to keep these alternatives in mind is an 
unfortunate fact of programming  life.

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

If you shift indexes down and substitute i = k+1, then i, 2*i, 2*i+1 are 
transformed to (k+1)-1, 2*(k+1)-1, 2*(k+1)+1-1 == k, 2*k+1, 2*(k+1).  So 
the Python invariant is the same thing in different 'coordinates'.

In the first case h1 is smaller than h2,h3; h2 smaller than h4,h5; etc.
In the second, h0 is smaller than h1,h2; h1 smaller than h3,h4, etc.

Terry Jan Reedy