treap: Efficient implementation of the implicit treap data structure

This is a package candidate release! Here you can preview how this package release will appear once published to the main package index (which can be accomplished via the 'maintain' link below). Please note that once a package has been published to the main package index it cannot be undone! Please consult the package uploading documentation for more information.

[maintain] [Publish]

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]

Properties

Versions	0.0.0.0, 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 Dmitrii Kovanikov
Author	Dmitrii Kovanikov
Maintainer	kovanikov@gmail.com
Category	Data Structure, 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:46:49Z

Modules

[Index] [Quick Jump]

Treap

Downloads

treap-0.0.0.0.tar.gz [browse] (Cabal source package)
Package description (as included in the package)

Maintainer's Corner

Package maintainers

vrom911

For package maintainers and hackage trustees

edit package information

Readme for treap-0.0.0.0

[back to package description]

treap

Treap: tree logo

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](https://www.flaticon.com/) is licensed by CC 3.0 BY.