treap-rs

随机化 treap 实现。

文档

示例

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

用法

将此添加到您的 Cargo.toml

[dependencies]
treap = "*"

并将此添加到您的 crate 根目录

extern crate treap;

lib.rs:

随机化 Treap

treap 是二叉树的一种变体。每个插入的键都会分配一个优先级，并且结果二叉树具有不变性，即它是一个根据键的键二叉搜索树，以及根据优先级的最大堆。

此实现是随机的，意味着优先级是随机分配的。treap 的期望深度为 O(log n)。