The Treap is a mix between a Binary Search Tree and a Heap.
Like a Binary Search Tree, it keeps an ordered set of keys in the shape of a tree, allowing for binary search traversal.
Like a Heap, it associates each node with a priority, making sure that a parent’s priority is always higher than any of its children.