treap: Efficient implementation of the implicit treap data structure
Efficient implementation of the implicit treap data structure. Use this data structure if you want dynamic arrays with fast operations on segments.
[Skip to Readme]
Downloads
- treap-0.0.0.0.tar.gz [browse] (Cabal source package)
- Package description (revised from the package)
Note: This package has metadata revisions in the cabal description newer than included in the tarball. To unpack the package including the revisions, use 'cabal get'.
| Versions [RSS] | 0.0.0.0 |
|---|---|
| Change log | CHANGELOG.md |
| Dependencies | base (>=4.11 && <4.13), deepseq (>=1.4 && <1.5), mersenne-random-pure64 (>=0.2.2 && <0.3) [details] |
| License | MPL-2.0 |
| Copyright | 2019-2021 Dmitrii Kovanikov |
| Author | Dmitrii Kovanikov |
| Maintainer | kovanikov@gmail.com |
| Revised | Revision 1 made by vrom911 at 2021-08-02T13:16:20Z |
| Category | Data Structures, Tree |
| Home page | https://github.com/chshersh/treap |
| Bug tracker | https://github.com/chshersh/treap/issues |
| Source repo | head: git clone https://github.com/chshersh/treap.git |
| Uploaded | by shersh at 2019-04-29T09:48:01Z |
| Distributions | NixOS:0.0.0.0 |
| Downloads | 437 total (1 in the last 30 days) |
| Rating | (no votes yet) [estimated by Bayesian average] |
| Your Rating | |
| Status | Docs available [build log] Last success reported on 2019-04-29 [all 1 reports] |
Readme for treap-0.0.0.0
[back to package description]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
takeordroporsplit.
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.