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?

  • $\begingroup$ 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? $\endgroup$
    – D.W.
    Nov 15 '19 at 4:40
  • $\begingroup$ I am thinking of a treap. $\endgroup$ Nov 15 '19 at 11:51

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.


This site is temporarily in read only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .