Suppose an inventory must support lookup by product name and quick access to products closest to running out. A binary search tree orders names; a heap puts the highest-priority stock quantity at its root. A treap combines those two rules in one tree, using a separate key and priority for each node. section 3.0 section 3.3
Figure 3.2 An example of a treap, with strings as BST keys and integers as heap priorities. Note that the heap, in this case, is a min-heap, so smaller numbers go on top. For a few links close to the root, we also show the range of keys that can be hosted in the tree’s branch rooted at the node they point to.
The diagram shows product names ordered left to right by the binary-search-tree rule and stock quantities ordered along root-to-leaf paths by a min-heap rule. section 3.3
Each node stores a key, a priority, and links to its children and parent. A key smaller than a node's key belongs in its left subtree; a larger key belongs in its right subtree. In a min-heap treap, a parent's priority is no greater than its children's. Linked nodes suit treaps better than an array: restoring these rules requires rotations that move whole subtrees by changing links. section 3.3 section 3.3.2
The core operations preserve both orderings:
- Search follows one branch at each node, comparing keys exactly as in an ordinary binary search tree. section 3.3.3
- Insert a key at its binary-search-tree leaf position, then rotate the new node upward while its priority outranks its parent's. Swapping entries as in an array heap would not preserve key order. section 3.3.4
- To delete, find the key, rotate its node downward until it becomes a leaf, then detach it. Rotating the higher-priority child upward maintains heap order. section 3.3.5
- Peek reads the root; top removes it. Minimum and maximum keys lie at the leftmost and rightmost nodes, which need not be leaves. section 3.3.6 section 3.3.7
Using stock quantity as priority is possible, but it does not reliably balance the tree. The principal use is a randomized treap: assign each newly inserted key an independently generated uniform random priority. This makes the expected height logarithmic without manually choosing priorities; it does not guarantee logarithmic height on every run. section 3.4 section 3.4.2
Except for peek, operations take O(h) time for tree height h; a skewed tree can make h = O(n). Randomized treaps fit dynamic sorted sets when average-case guarantees are acceptable. They can cost more memory and, when a plain tree is already well shaped, more running time than a plain binary search tree. Measure the workload before choosing. section 3.3.8 section 3.4.3 section 3.5.5
