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?

• I don't understand what you are getting at. Sets have elements; there is no notion of priorities. Perhaps you are thinking of a priority queue rather than a set?
– D.W.
Nov 15 '19 at 4:40
• I am thinking of a treap. Nov 15 '19 at 11:51