A treap is a binary search tree $($BST$)$ which additionally maintains heap priorities. An

example is given in Figure $1.$ A node consists of

$$ A key k $($given by the letter in the example$),$

$$ A random heap priority p $($given by the number in the example$).$ The heap priority p

is assigned at random upon insertion of a node. It should be unique in the treap.

$$ A pointer to the left child and to the right child node,

For example, the root node in the treap in Figure $1$ has $$h$$ as key and $9$ as heap priority.

Note that if you insert just the keys of the treap in Figure $1$ into an empty BST$,$ selecting

each node based on the priority $($from max to min$),$ you get back a BST of the exact same

form as the treap. For example, if you insert the keys $[$h;j;c;a;e$]($in that order$)$ into an empty

BST$,$ then you get back a tree just like that in Figure $1.$ Since the priorities are chosen at

random, treaps may be understood as random BSTs$.$

The good thing about random BSTs is that they are known to have logarithmic height

with high probability. Thus the same is true for treaps. Indeed, on average