Treap #

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 set operations, it allows for:

• select(i) – find the i-th smallest element.
• rank(x) – find the rank of element x, i.e. the number of elements smaller than x.

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.

Example #

A 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