treap.py is a python module (more than one actually) for implementing a "treap", which is a datastructure that is a hybrid of a binary heap and a binary tree.

It was originally GPLv3-licensed, but now it's Apache v2 licensed.

This treap module is designed to have a dictionary-like interface:

However, it's also ordered:

It comes with a pure python version, and a version that has the more computationally-intensive portion in cython. The two are automatically derived from a single m4-preprocessed file.

Here's a table comparing the asymptotic running time of various python datastructures across a variety of operations. As you can see, like any datastructure it's not stellar at everything, but it does have a nice set of tradeoffs:

If asymtoptic running time is something you don't want to think about, you might just consider that running times can be sorted like the following, for large inputs, where O(1) is fastest and O(n*log2(n)) is slowest:

The download also comes with a "nest.py" module, that's intended to make it easy to keep the lowest (or highest) p objects (objects having a __cmp__ method) out of a collection of q objects.

Looking for duptreaps? Check out dupdict_mod.

See also this list of datastructures I've worked on.


5975

Back to Dan's tech tidbits

You can e-mail the author with questions or comments: