I've just released my treap.py module:
http://stromberg.dnsalias.org/~dstromberg/treap/
It's code that implements a datastructure that is a hybrid of a binary
tree and a binary heap, having some of the advantages of each. The URL
has a table comparing the asymptotic performance of treaps against some
other common python datastructures.
This particular implementation is pretty dicitionary-like, but you can
also get the smallest value or the largest value in O(log2(n)) time, or
get a forward or reverse ordered list of values in O(n) time. The price
of course is that adding and deleting things is O(log2(n)) time.
It's currently GPLv3-licensed, but I'd like to dual license it in such a
way that it could eventually be included in the standard library. How
would I go about this?
Also, what's the best way to package something like this for consumption
by python-folk? There seem to be so many ways of packaging things
anymore. Are dist utils, a .deb and a .rpm the way to go? Right now,
it's just using make to stuff things in /usr/local.
There are two versions: One that is pure python, and one that is part
python and part cython. They're automatically generated from a common
m4 template.
There are rather plentiful unit tests included in the tar archive.
I hope someone besides me finds it useful.
--
http://mail.python.org/mailman/listinfo/python-list
