in examples i've seen on web, taken given there's sort of external random number generator yield random (distinct!) priorities.
from recall, there method generate priorities randomly , when inserting them down treap untie possible priorities clashes on-the-go.
i have 2 questions, then:
- do treaps need have priorities distinct, or priorities of nodes may end being compared? is, if have 2 nodes priority
pcan make sure never meet in way, there problem in having them have same priority? - how should go generating , untying priorities in treap?
thanks
edit: here's description of i'm talking about:
problem 8.12 @ randomized algorithms
let analyze number of random bits needed implement operations of treap. suppose pick each priority pi uniformly @ random unit interval [0,1]. then, binary representation of each pi can generated (potentially infinite) sequence of bits outcome of unbiased coin flips. idea generate many bits in sequence necessary resolving comparisons between different priorities. suppose have generated prefixes of binary representations of priorities of elements in treap t. now, while inserting item y, compare priority py others' priorities determine how y should rotated. while comparing py pi. if current partial binary representation can resolve comparison, done. otherwise. have same partial binary representation , keep generating more bits each till first differ.
priorities may equal. it's suboptimal so, low-collision random number generator preferred, checking slower accepting random chance of collision.
a priority assigned key when first inserted treap. in order preserve structure of treap make sure tree remains heap-ordered on priorities after every operation. is, after every operation make sure every nodes priority greater or equal priority of children.
