The MkTreapDict functor

« 210 Library Documentation

Overview

functor MkTreapDict (structure Key : ORDKEY)
:> SORTED_DICT where Key = Key and Seq = ArraySequence

functor MkTreapSet (structure Key : ORDKEY)
:> SORTED_SET where Key = Key and Seq = ArraySequence

Implements sorted dictionaries as treaps, built with MkTreap. MkTreapSet implements sorted sets as dictionaries with values of type unit, and its operations have the same costs as the dictionary's, with contains costing what find does.

SORTED_DICT and SORTED_SET Cost Specifications

The following costs assume that comparing and hashing keys take constant work and span.

* With high probability. † In expectation. Unmarked bounds are deterministic.
Work Span
empty $()$
singleton $(k, v)$
size $d$ 		$O(1)$ $O(1)$
fromSeq $s$ $O(|s|\log|s|)$* $O(\log^2|s|)$*
toSeq $d$ $O(|d|)$ $O(\log|d|)$*
find $d\ k$
insert $(d, (k, v))$
remove $(d, k)$ 		$O(\log|d|)$* $O(\log|d|)$*
filter $p\ d$ $\displaystyle \sum_{(k \mapsto v) \in d} \mathcal{W}(p(k,v))$† $\displaystyle O(\log^2|d|) + \max_{(k \mapsto v) \in d} \mathcal{S}(p(k,v))$*
first $d$
last $d$
prev $(d, k)$
next $(d, k)$
split $(d, k)$
getRange $d\ (k_1, k_2)$
rank $(d, k)$
select $(d, i)$ 		$O(\log|d|)$* $O(\log|d|)$*
join $(a, b)$ $O(\log(|a| + |b|))$* $O(\log(|a| + |b|))$*

In the following, $n$ and $m$ are the sizes of the arguments with $m \leq n$.

* With high probability. † In expectation.
Work Span
union $(a, b)$
intersection $(a, b)$
difference $(a, b)$ 		$\displaystyle O\left(m\log\left(1+\frac{n}{m}\right)\right)$† $O(\log(n+m))$*