Treap
= Treap
A treap is a binary search tree ordered by keys and simultaneously a <binary heap> ordered by priorities. Independent random priorities give logarithmic expected search depth. An implicit treap uses subtree sizes to address sequence positions instead of storing explicit keys.