**Monthly Downloads**: 2

**Programming language**: Haskell

**License**: Mozilla Public License 2.0

**Latest version**: v0.0.0.0

## treap alternatives and similar packages

Based on the "Data Structure" category

*Do you think we are missing an alternative of treap or a related project?*

## README

## treap

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)
`insert`

/`delete`

/`split`

/`merge`

/`take`

/`drop`

/`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
`take`

or`drop`

or`split`

.

Below you can find the table of time complexity for all operations (where `n`

is
the size of the treap):

Operation | Time complexity | Description |
---|---|---|

`size` |
`O(1)` |
Get number of elements in the treap |

`at` |
`O(log n)` |
Access by index |

`insert` |
`O(log n)` |
Insert by index |

`delete` |
`O(log n)` |
Delete by index |

`query` |
`O(log n)` |
Measure monoid on the segment |

`splitAt` |
`O(log n)` |
Split treap by index into two treaps |

`merge` |
`O(log n)` |
Merge two treaps into a single one |

`take` |
`O(log n)` |
Take first `i` elements of the treap |

`drop` |
`O(log n)` |
Drop first `i` elements of the treap |

`rotate` |
`O(log n)` |
Put first `i` elements to the end |

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
```

## Alternatives

If you don't need to calculate monoidal operations, you may alternatively use
`Seq`

from the `containers`

package as it provides more extended interface but doesn't
allow to measure monoidal values on segments.

## Acknowledgement

Icons made by Freepik from www.flaticon.com is licensed by CC 3.0 BY.

*
*Note that all licence references and agreements mentioned in the treap README section above
are relevant to that project's source code only.
*