Have you read the Python docs lately?

[Dan Stromberg]

On Wed, Apr 27, 2011 at 10:56 AM, Raymond Hettinger <python at rcn.com> wrote:
> A number of developers have been working on adding examples and useful
> advice to the docs.  To sharpen your skills, here are some pieces of
> recommended reading:
>
> http://docs.python.org/dev/library/heapq.html#priority-queue-implementation-notes

I believe there isn't any reason why a heap _has_ to be stored in an
array - it's just one of the best representations.  Or so I was taught
in school.  Though granted, in _Python_ most heaps are arrays, because
the standard library implements them as arrays - perhaps this is what
was meant.

> http://docs.python.org/dev/library/bisect.html#searching-sorted-lists
>
> http://docs.python.org/dev/library/re.html#writing-a-tokenizer
>
> http://docs.python.org/dev/library/cmd.html#cmd-example
>
> http://docs.python.org/dev/library/collections.html#ordereddict-examples-and-recipes

Boy, all this sorting...  It seems like it'd be better to use a treap
or red black tree, even when you take into account that Python's sort
will tend to handle adding a single value in O(n) time - because the
treap or red black tree should handle the task in O(logn) time with a
low constant.

http://stromberg.dnsalias.org/~strombrg/treap/
http://newcenturycomputers.net/projects/rbtree.html

A treap should give better average case time than a red black tree,
but a red black tree should give a decent average case with less time
variability.

> http://docs.python.org/dev/howto/logging.html
>
> http://docs.python.org/dev/howto/sorting.html
>
> http://docs.python.org/dev/library/collections.html#collections.namedtuple