A randomized BST where each node has a key (BST order) and a random priority (heap order). Rotations maintain both invariants — expected O(log n) operations.
Insert keys to build the treap. BST property by key (left=smaller), heap property by priority (parent=higher).