treap alternatives and similar packages
Based on the "Data Structure" category.
Alternatively, view treap alternatives based on common mentions on social networks and blogs.
Do you think we are missing an alternative of treap or a related project?
Efficient implementation of the implicit treap data structure.
What does this package provide?
This package implements a tree-like data structure called implicit treap. This
data structure implements interface similar to random-access arrays, but with
fast (logarithmic time complexity)
rotate operations. In addition,
treap allows you to specify and measure values of any monoids on a segment,
like a sum of elements or minimal element on some contiguous part of the array.
When to use this package?
Use this package when you want the following operations to be fast:
- Access elements by index.
- Insert elements by index.
- Delete elements by index.
- Calculate monoidal operation (like sum, product, min, etc.) of all elements between two indices.
- Call slicing operations like
Below you can find the table of time complexity for all operations (where
the size of the treap):
||Get number of elements in the treap|
||Access by index|
||Insert by index|
||Delete by index|
||Measure monoid on the segment|
||Split treap by index into two treaps|
||Merge two treaps into a single one|
The package also comes with nice pretty-printing!
ghci> t = fromList [1..5] :: RTreap (Sum Int) Int ghci> prettyPrint t 5,15:2 ╱╲ ╱ ╲ ╱ ╲ ╱ ╲ 1,1:1 3,12:4 ╱╲ ╱ ╲ ╱ ╲ 1,3:3 1,5:5
If you don't need to calculate monoidal operations, you may alternatively use
containers package as it provides more extended interface but doesn't
allow to measure monoidal values on segments.
*Note that all licence references and agreements mentioned in the treap README section above are relevant to that project's source code only.