After this insertion, x will be the root node of the treap, all values less than x will be found in the left subtreap, and all values greater than x will be found in the right subtreap. This costs as much as a single insertion into the treap. Joining two treaps that are the product of a former split, one can safely assume that the greatest value in the first treap is less than the smallest value in the second treap. Create a new node with value x, such that x is larger than this max-value in the first treap and smaller than the min-value in the second treap, assign it the minimum priority, then set its left child to the first heap and its right child to the second heap. Rotate as necessary to fix the heap order. After that, it will be a leaf node, and can easily be deleted. The result is one treap merged from the two original treaps. This is effectively "undoing" a split, and costs the same. More generally, the join operation can work on two treaps and a key with arbitrary priority (i.e., not necessary to be the highest). The join algorithm is as follows: function join(L, k, R) if prior(k, k(L)) and prior(k, k(R)) return Node(L, k, R) if prior(k(L), k(R)) return Node(left(L), k(L), join(right(L), k, R)) return Node(join(L, k, left(R)), k(R), right(R)) The split algorithm is as follows: function split(T, k) if (T = nil) return (nil, false, nil) (L, (m, c), R) = expose(T) if (k = m) return (L, true, R) if (k < m) (L', b, R') = split(L, k) return (L', b, join(R', m, R)) if (k > m) (L', b, R') = split(R, k) return (join(L, m, L'), b, R')) The union of two treaps and , representing sets and is a treap that represents . The following recursive algorithm computes the union: function union(t1, t2): if t1 = nil: return t2 if t2 = nil: return t1 if priority(t1) < priority(t2): swap t1 and t2 t<, t> ← split t2 on key(t1) return join(union(left(t1), t<), key(t1), union(right(t1), t>)) Here, split is presumed to return two trees: one holding the keys less than its input key, one holding the greater keys. (The algorithm is non-destructive, but an in-place destructive version exists as well.) The algorithm for intersection is similar, but requires the join helper routine. The