treap

If v is a left child of u, then v.key < u.key
If v is a right child of u, then v.key > u.key
If v is a child of u, v.priority > u.priority
(This combination of properties is why the tree is called a "treap": it has features of both a binary search tree and a heap.)