Treap Properties

A treap maintains two properties:

$1.$ BST property: for every node, left subtree keys < node key < right subtree keys

$2.$ Heap property: for every node, node priority > children priorities

These properties uniquely determine the tree structure given keys and priorities. If you assign random priorities, the resulting tree is equivalent to a BST built by inserting keys in random order. Random order insertion gives expected $O(\log n)$ height. The treap achieves this without actual randomization of insert order.