<[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED] | | >> 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 -- http://mail.python.org/mailman/listinfo/python-list
