What is a Treap and how does it combine BST and heap properties?

A Treap is a randomized BST where each node has a key (BST property) and a random priority (heap property). Keys maintain BST ordering; priorities maintain max-heap ordering with parents having higher priority than children. This random structure provides expected O(log n) height without explicit balancing. Operations use tree rotations to maintain heap property after BST operations. Treaps support split and merge operations naturally, useful for implementing rope data structures.