[docs] Heapq documentation bug

[Johannes Hoff]

On Tue, Nov 23, 2010 at 9:37 AM, Georg Brandl <georg at python.org> wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> Am 22.11.2010 11:02, schrieb Johannes Hoff:
>> Hi,
>>
>> There is, in my opinion, a bug in the documentation for heapq, for all
>> versions of this module [1].
>>
>> The documentation states the following:
>>
>>> Heaps are arrays for which heap[k] <= heap[2*k+1] and heap[k] <= heap[2*k+2] for all k
>>
>> In this context, I would say that "heaps" clearly refers to the
>> general concept, not this particular implementation. In that case, it
>> is not correct to say that heaps are arrays - they are trees. They are
>> often implemented as arrays, but they need not be.
>>
>> Sources:
>> http://en.wikipedia.org/wiki/Heap_(data_structure)
>> http://c2.com/cgi/wiki?HeapDataStructure
>>
>> Suggested wording:
>>
>>> Heaps are trees for which every parent node has a value less than or equal to any of its children. This implementation uses an array for which heap[k] <= heap[2*k+1] and heap[k] <= heap[2*k+2] for all k, counting elements from zero. For the sake of comparison, non-existing elements are considered to be infinite. The interesting property of heaps is that the smallest element is always the root, in this case heap[0].
>>
>> Or, dropping the general case:
>>
>>> This implementation stores the heap in an array for which heap[k] <= heap[2*k+1] and heap[k] <= heap[2*k+2] for all k, counting elements from zero. For the sake of comparison, non-existing elements are considered to be infinite. The smallest element of the heap will always be at the root, heap[0].
>
> Hi Johannes,
>
> thanks for your suggestion; it has now been applied to the development docs.

Thanks!

Just one little thing. It now says:

> Heaps are binary trees for which...

You can drop the "binary" -- the algorithm works on trees in general
(with a bound number of children).

Johannes