treap: Efficient implementation of the implicit treap data structure

[ data-structures, library, mpl, tree ] [ Propose Tags ]

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]
Versions [RSS] [faq] 0.0.0.0
Change log CHANGELOG.md
Dependencies base (>=4.11 && <4.13), deepseq (==1.4.*), 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 380 total (8 in the last 30 days)
Rating (no votes yet) [estimated by Bayesian average]
Your Rating
  • λ
  • λ
  • λ
Status Hackage Matrix CI
Docs available [build log]
Last success reported on 2019-04-29 [all 1 reports]

Modules

[Index] [Quick Jump]

Downloads

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'.

Maintainer's Corner

For package maintainers and hackage trustees

Candidates


Readme for treap-0.0.0.0

[back to package description]

treap

Treap: tree logo Hackage Build status MPL-2.0 license

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:

  1. Access elements by index.
  2. Insert elements by index.
  3. Delete elements by index.
  4. Calculate monoidal operation (like sum, product, min, etc.) of all elements between two indices.
  5. 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.