What is a Treap? How does it combine BST and Heap properties?

Difficulty: 6/10

BST property, heap property, randomized balancing

Treap

A Treap combines the binary-search-tree property on keys with a heap property on randomly assigned priorities. The key determines left/right ordering, while priority determines the heap ordering. Random priorities make the expected height O(log n), giving expected logarithmic search, insertion, and deletion.

javascript

1
BST ordering applies to keys.
2
Heap ordering applies to priorities.
3
Random priorities provide expected balancing.
4
Expected operations: O(log n).
5
Rotations maintain both invariants.

Scenario Questions

0-2 years experience

2-5 years experience

Follow-up Questions