2

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.

devoured elysium
  • 101,373
  • 131
  • 340
  • 557

2 Answers2

1

  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.

orlp
  • 112,504
  • 36
  • 218
  • 315
  • Hi, thanks for the answer. I am well aware of point 2, but that was not really my question. Let me attempt to rephrase it. I've heard of a method where you generate random bits for the priority of the nodes, and if you find that there is some tie between two nodes, you generate extra bits on both priorities until the tie is over. The idea is that you are actually sure there are no ties when inserting/deleting a node. I've looked over the web and I have not seen it referred anywhere. I've seen it vaguely referred in the Randomized Algorithms book, but I didn't quite get the explanation. – devoured elysium Apr 28 '15 at 03:11
  • @devouredelysium If that is indeed a method advocated by some, I believe that it is suboptimal. The storage for the priority is limited - you can't simply generate extra random bits, because there is no storage for them in the node. If you do have extra storage you should just generate more random bits when you insert the node. – orlp Apr 28 '15 at 03:15
  • @devouredelysium You're confused. The paragraph you cited does not indicate an implementation strategy at all. It's a mathematical tool to do complexity analysis on the Treap - it's purely theoretical. – orlp Apr 28 '15 at 03:21
  • Hmmm.. I'll straight this up tomorrow in class. – devoured elysium Apr 28 '15 at 03:33
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
David Eisenstat
  • 64,237
  • 7
  • 60
  • 120