heap doesn't appear to work as described

[7stud]

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.

[skip]

>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

[7stud]

On Apr 3, 5:27 pm, [e-mail] wrote:

>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

Thanks

[Terry Reedy]

<sk**@pobox.comwrote in message
news:17***********************@montanaro.dyndns.or g...
|
| >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

[7stud]

On Apr 3, 10:30 pm, "Terry Reedy" <[e-mail]:

<[e-mail] in message

news:17***********************@montanaro.dyndns.or g...
|
| >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.

My book uses lists.

[skip]

skipCheck the heapq docs for the constraints the Python heapq module
skipmaintains:

s/constraints/invariants/

Skip

[skip]

>>>My book says that in a heap, a value at position i will be 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.

My book uses lists.

Yes, but is the first element of the list addressed as element 1 or element
0? Terry was doing the transformation from 1-based to 0-based indexing to
demonstrate that the invariants you described were the same as those
maintained by Python's heapq module.

Skip

[7stud]

On Apr 4, 7:05 am, [e-mail] wrote:

>>>My book says that in a heap, a value at position i will be 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.

My book uses lists.

Yes, but is the first element of the list addressed as element 1 or element
0?

Here is the example:
---------
from heapq import *
from random import shuffle

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

#my test:
print heap[0] #output: 0
-------

It's from Beginning Python: Novice to Professional, which I think is a
really poorly written book chock full of mistakes and ambiguous
example code.