Treap

Treap is a randomized binary search tree. Each treap's node contains two parameters: key (which is used for binary search) and priority (which is chosen randomly). While keys are used as BST operator priorities are used as Heap operator (hence the name treap: tree + heap)

Sources:

• https://cp-algorithms.com/data_structures/treap.html
• https://e-maxx.ru/algo/treap
• https://www.geeksforgeeks.org/treap-a-randomized-binary-search-tree
• https://en.wikipedia.org/wiki/Treap

Table of Contents

• Usage
• Project Hierarchy
• Testing
• JMH
  • Configuration
  • Execution

Usage

The main implementation is TreapSet, which implements java.util.Set:

public static void main(String[] args) {
    Set<Integer> set = new TreapSet<>();
    set.add(3);
    set.add(1);
    set.add(4);

    System.out.println(set);
}

Output:

TreapSet{array=[1, 3, 4]}

It implements interface Treap, which extends java.util.Set:

public static void main(String[] args) {
    Treap<Integer> treap = new TreapSet<>();
    treap.add(3);
    treap.add(1);
    treap.add(4);
    treap.add(2);
    treap.add(5);

    Reference<Treap<Integer>> left = new Reference<>();
    Reference<Treap<Integer>> right = new Reference<>();

    treap.split(3, left, right, Inclusion.RIGHT);

    System.out.println(String.format("left: %s", left));
    System.out.println(String.format("right: %s", right));
}

Output:

left: TreapSet{array=[1, 2]}
right: TreapSet{array=[3, 4, 5]}

Project Hierarchy

.
└── lib
    ├── build.gradle
    ├── gradle
    │   └── wrapper
    │       ├── gradle-wrapper.jar
    │       └── gradle-wrapper.properties
    ├── gradlew
    ├── gradlew.bat
    ├── jmh.gradle                         # JMH configuration
    ├── settings.gradle
    └── src
        ├── jmh                            # JMH sources
        ├── main                           # library sources
        └── test                           # test sources

Testing

./lib/gradlew clean test -p ./lib

JMH (jmh-gradle-plugin)

Configuration

To configure JMH execution jmh.gradle can be used:

jmh {
    warmupForks = 2
    warmupIterations = 4
    iterations = 4
    fork = 4
}

List of all configuration options is here

Execution

./lib/gradlew --no-daemon clean jmh -p ./lib