Q:

Treap union unrandomizes priorities?

The algorithm for the union of two sets represented by treaps is defined in this paper and on Wikipedia, but the algorithm seems flawed.
Take for example the following loop.
X := {a}
for (i := 0; i < 1000; i := i + 1)
  X := X ∪ {a}

At the end of execution, the variable $X$ contains the set $\{a\}$, but the priority of the element $a$ is elevated and not random because the union algorithm always picks the element with the highest priority.
Am I missing something?

A:

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.

