What is a treap? — Tree + heap 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.