Two structures in one
A treap combines a binary search tree on keys with a heap on priorities. Each node stores a key and a randomly chosen priority. The tree obeys the search tree order on keys and the heap order on priorities: every node's priority is at least as large as its children's.
Why random priorities balance it
Once keys and priorities are fixed, the treap's shape is uniquely determined. Because the priorities are random, the expected shape is the same as a randomly built search tree, whose expected height is logarithmic. So the tree balances itself without any explicit balance bookkeeping.
Operations by rotation
- Insert: place the key as a normal leaf, then rotate it upward while its priority is larger than its parent's, restoring heap order.
- Delete: rotate the target down until it becomes a leaf, then snip it off.
- Split and merge: treaps support cutting the set at a key and joining two sets, which makes them handy for ordered collections.
Key idea
Layering a random priority heap on top of a search tree yields expected logarithmic height with simple rotation based code.