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.
New to topics? Read the docs here!