2 releases
Uses old Rust 2015
0.0.2 | Dec 10, 2016 |
---|---|
0.0.1 | Dec 10, 2016 |
#7 in #randomized
22KB
445 lines
treap-rs
A randomized treap implementation.
Example
extern crate treap;
use treap::TreapMap;
fn main() {
let mut t = TreapMap::new();
for i in 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));
}
Usage
Add this to your Cargo.toml
:
[dependencies]
treap = "*"
and this to your crate root:
extern crate treap;
lib.rs
:
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).
Dependencies
~315–540KB