3 releases

Uses old Rust 2015

0.0.3 Feb 21, 2015
0.0.2 Feb 10, 2015
0.0.1 Feb 9, 2015

#52 in #set

MIT license

414 lines


Build Status

A randomized treap implementation.



extern crate treap;

use treap::TreapMap;

fn main() {
    let mut t = TreapMap::new();

    for i in range(0, 10) {
        t.insert(i, i);

    for (k, v) in &mut t {
        *v = *v * *v;

    assert_eq!(t.get(&5), Some(&25));
    assert_eq!(t.remove(&3), Some(9));


Add this to your Cargo.toml:

treap = "*"

and this to your crate root:

extern crate treap;


Randomized Treap

A treap is a variation of a binary tree. Each inserted key is assigned a priority and the resulting binary tree has the invariant that it is a binary search tree with respect to the keys and a max-heap with respect to the priorities.

This implementation is randomized meaning that the priorities are assigned at random. The treap has an expected depth of O(log n).