Treap库

Treap（Aragon和Siedel '89，随机搜索树）是一种二叉搜索树。二叉搜索树中的每个元素都包含一个值和一个优先级，该算法保证了以下两点：（a）二叉搜索树按照值进行排列，因此在（理想情况下），可以在O(lg n)的时间内找到值（或检查其存在性）。（b）二叉树的根始终是具有最大“优先级”的元素。

传统上使用随机优先级，因此期望上树是平衡的。然而，Treap并不是构建集合或哈希表的特别有趣的方式，你最好使用标准的Rust BTree。

此实现的存在是为了在需要同时访问具有最大优先级的元素和检查存在性的情况下使用，就像CVM算法（https://cs.stanford.edu/~knuth/papers/cvm-note.pdf）一样。

示例

use treap_non_random as treap;
use treap::{Element, Treap};

let mut t: Treap<String, i32> = Treap::new();
t.insert(Element::new("A".into(), 0));
t.insert(Element::new("lo".into(), -22));
t.insert(Element::new("hi".into(), 65536));
let max = t.get_max();
assert!(max.is_some() && max.unwrap().value().eq("hi".into()));
let lo = t.get("lo".into());
assert!(lo.is_some());
let no = t.get("missing".into());
assert!(no.is_none());