Expand description
A Treap library
A treap (Aragon and Siedel ’89, Randomized Search Tree) is a binary search tree. Each element in the binary search tree contains a value and a priority, and the algorithm guarantees two things: (a) The binary search tree is arranged according to values, and thus in (good cases), you can find a value (or check for its existence) in O(lg n) time. (b) The root of the binary tree is always the element with the largest “priority”.
Traditionally, random priorities are used and thus in expectation the tree is balanced. However, Treaps are not a particularly interesting way to build sets or hashmaps, you are better served using the standard Rust BTree instead.
This implementation exists instead to be used in cases where accessing elements with max priorities and checking existence are both necessary, as is the case with the CVM algorithm (https://cs.stanford.edu/~knuth/papers/cvm-note.pdf).
§Example
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());