A package implementing a persistent (immutable) order statistic tree by means of the treap data structure (a kind of cartesian tree). Apart from the regular binary tree operations, it allows for:
select(i)– find thei-th smallest element.rank(x)– find the rank of elementx, i.e. the number of elements smaller thanx.
both in O(log(N)) time.
This particular implementation is made fully persistent by means of path copying. That is, any operation that would otherwise mutate the treap, instead produces a new treap, and does so using only O(log(N)) extra space. This allow copies to be O(1) in time and space.
TreapSet<T> (build on top of Treap<T>) implements Set<T>. It resembles SplayTreeSet<T> in behavior, keeping elements ordered, but it differs in performance of:
take,skip, andelementAt,
which are all O(log(N)) (given select and rank) and toSet which is O(1).
Hence it is much faster than all the 3 standard sets LinkedHashSet (default), HashSet and SplayTreeSet on these operations.
The advantage naturally grows with N (no of items), but LinkedHashSet<int> is already a bit behind for N = 10, and Treap stays below 1us for N = 1000000 on all these 4 operations (as tested on my old 2,4 GHz 8-Core Intel Core i9 MacBook Pro).
However there is no such thing as free lunch.
As a rule of thumb the mutating operations add, remove, etc. are roughly twice as slow as for SplaySetTree (which is already a lot slower than HashSet and LinkedHashSet).
This is mostly due to the cost of the path copying done to make Treap<T> immutable, and the fact that HashSet and LinkedHashSet is implemented directly in the runtime.
A full benchmark suite can be found in benchmark/main.dart comparing various set operations on the three standard sets and TreapSet.
Run with
dart run --no-enable-asserts benchmark/main.dartA toy todo flutter app, that illustrates how to use persistent treaps to efficiently handle undo/redo and animate a list view.
If your browser supports WasmGC (such as Chrome 119+, or Firefox 120+), you can try out the app here