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]

 

[skip]

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]

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]

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

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

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

s/constraints/invariants/

Skip

 

[skip]

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

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