trp.h -- Treap implementation

trp.h implements treaps using a simple pseudo-random number generator (PRNG) for priorities. An alternative trp.h implements treaps using Bob Jenkins's lookup3.h hashing implementation to generate priorities by hashing pointers. The PRNG-based implementation is more portable, but tree nodes are larger, due to explicitly stored node priorities. For discussion, see this blog post.

For those concerned about correctness and performance, test programs (PRNG, hash) and benchmark programs (PRNG, hash) are available.

Copyright © 2008 Jason Evans <>.
Last updated Friday 2008/07/26 00:14:40 (PDT)


PRNG-based trp.h
Hash-based trp.h