How to generate random priorities for Treap nodes?

Question

In most examples I've seen on the web, it is taken as given that there's some sort of external random number generator that will yield random (distinct!) priorities.

From what I recall, there was a method to actually generate the priorities randomly and when inserting them down the treap to untie possible priorities clashes on-the-go.

I have two questions, then:

1. Do the treaps actually need to have its priorities all distinct, or only the priorities of nodes that may end up being compared? That is, if I have two nodes with a priority p but I can make sure they will never meet in any way, is there a problem in having them have the same priority?
2. How should I go about generating and untying priorities in my treap?

Thanks

EDIT: Here's a description of what I'm talking about:

Problem 8.12 @ Randomized Algorithms

Let us now analyze the number of random bits needed to implement the operations of a treap. Suppose we pick each priority Pi uniformly at random from the unit interval [0,1]. Then, the binary representation of each Pi can be generated as a (potentially infinite) sequence of bits that are the outcome of unbiased coin flips. The idea is to generate only as many bits in this sequence as is necessary for resolving comparisons between different priorities. Suppose we have only generated some prefixes of the binary representations of the priorities of the elements in the treap T. Now, while inserting an item y, we compare its priority Py to others' priorities to determine how y should be rotated. While comparing Py to some PI. if their current partial binary representation can resolve the comparison, then we are done. Otherwise. they have the same partial binary representation and we keep generating more bits for each till they first differ.

Answer 1

1. You can do whatever you want with the priorities without impacting correctness -- it's still a binary search tree underneath it all. It's possible (but more complicated) to redo the running time analysis to handle a small probability of priority collisions without sacrificing the O(log n) asymptotic bound.

2. Here's what the comparison operator might look like in Python. Initially priorities are [], the empty list, and the bits are filled in lazily as described. I'm using lists of bits; for more efficiency, it would be wise to pack them into larger integral types.

   import random
   
   def less(lst1, lst2):
       j = 0
       while True:
           if j >= len(lst1):
               lst1.append(random.randrange(2))  # random bit
           if j >= len(lst2):
               lst2.append(random.randrange(2))
           if lst1[j] != lst2[j]:
               return lst1[j] < lst2[j]
           j += 1
   

Answer 2

1. Priorities may be equal. It's suboptimal to do so, so a low-collision random number generator is preferred, but checking for it is slower than just accepting the random chance of a collision.

2. A priority is assigned to a key when it is first inserted into the treap. In order to preserve the structure of the treap you will make sure the tree remains heap-ordered on the priorities after every operation. That is, after every operation you make sure that every nodes priority is greater than or equal to the priority of its children.