What is a treap? — A random priority is assigned to every key and must maintain two properties: -They are in order with respect to their keys, as in a typical binary search tree -They are in heap order with respect to their priorities, that is, no key has a key of lower priority as an ancestor O(log N) expected time for all operations, O(N) worst case.