Treap

Aka: randomized search tree

A probabilistic data structure that combines a heap and a binary search tree. The priority of each node is randomly given and will lead to a randomly distributed binary search tree. Remember that the worst case scenario for a unbalanced binary search tree is inserting items in order; this randomization should minimize that scenario.

In order to maintain max-heap order, heap rotation will be performed during insertion and deletion.

Pros	Cons
Simpler than balanced binary search trees	Worst case is linear
Heap functionality	Randomized