Treap union unrandomizes priorities?
My question was answered by email after I posted it here.

The answer is that the priorities of the elements can't be chosen completely randomly when an element is inserted into the treap that represents the set. The priorities need to be given by a hash function. That way, the same elements are always associated with the same priorities and the union algorithm, which always picks the element with the highest priority, doesn't return a biased treap.