### 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

20KB

414 lines

# treap-rs

A randomized treap implementation.

## Example

`
``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``)``)``;`
`}`

## 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

~465KB