[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