[docs] Heapq documentation bug
Georg Brandl
georg at python.org
Tue Nov 23 09:37:56 CET 2010
-----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.
regards,
Georg
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.16 (GNU/Linux)
iEYEARECAAYFAkzrfWQACgkQN9GcIYhpnLClXACaAie2h9tfhB2zLq0lBpgzTWMW
LHwAoIzdd3XTUnh5MvbVD9h/C5xSG12i
=UufP
-----END PGP SIGNATURE-----
More information about the docs
mailing list