Treaps (Cartesian tree)

Tree + Heap = Treap
X values are keys
Y values are priorotoes
It is a way to balance BST and is called randomized binary serach tree

Operations

split(node, key) O(log(n))
merge(A, B) O(log(n))
insert(key) O(log(n))
find(key) O(log(n))
remove(key) O(log(n))

Links