Introduction
A treap is a data structure that combines a binary search tree and a binary heap. The name comes from tree + heap.
More precisely, a treap stores pairs so that:
- it is a binary search tree by ;
- it is a heap by .
So if a node contains , then:

