Как генерировать случайные приоритеты для узлов Treap?

Question

В большинстве примеров, которые я видел в Интернете, считается, что существует какой-то внешний генератор случайных чисел, который будет выдавать случайные (разные!) Приоритеты.

Из того, что я помню, был метод для фактической генерации приоритетов случайным образом и при вставке их в цепочку, чтобы развязать возможные приоритеты, столкновения на ходу.

У меня есть два вопроса:

1. Должны ли на самом деле трепы иметь все свои приоритеты или только приоритеты узлов, которые могут в конечном итоге сравниваться? То есть, если у меня есть два узла с приоритетом p но я могу быть уверен, что они никогда не встретятся, есть ли проблема в том, что они имеют одинаковый приоритет?
2. Как мне начать создавать и распаковывать приоритеты в моем трепе?

Спасибо

РЕДАКТИРОВАТЬ: Вот описание того, о чем я говорю:

Задача 8.12 @ Рандомизированные алгоритмы

Давайте теперь проанализируем количество случайных битов, необходимых для реализации операций трэпа. Предположим, что мы выбираем каждый приоритет Pi равномерно случайным образом из единичного интервала [0,1]. Затем двоичное представление каждого Pi может быть сгенерировано как (потенциально бесконечная) последовательность битов, которые являются результатом несмещенных бросков монет. Идея состоит в том, чтобы генерировать только столько битов в этой последовательности, сколько необходимо для разрешения сравнений между различными приоритетами. Предположим, что мы сгенерировали только некоторые префиксы двоичных представлений приоритетов элементов в трепе T. Теперь, вставляя элемент y, мы сравниваем его приоритет Py с приоритетами других, чтобы определить, как следует вращать y. Сравнивая Py с некоторым PI. если их текущее частичное двоичное представление может разрешить сравнение, то мы закончили. Иначе. они имеют одно и то же частичное двоичное представление, и мы продолжаем генерировать больше битов для каждого, пока они сначала не будут различаться.

Answer 1

1. Приоритеты могут быть равными. Это неоптимально, поэтому предпочтителен генератор случайных чисел с низким уровнем коллизий, но проверка его происходит медленнее, чем просто принятие случайного шанса на столкновение.

2. Приоритет назначается клавише, когда она впервые вставляется в трепан. Чтобы сохранить структуру трэпа, вы должны следить за тем, чтобы дерево оставалось упорядоченным по приоритетам после каждой операции. То есть после каждой операции вы должны убедиться, что приоритет каждого узла больше или равен приоритету его дочерних узлов.

Answer 2

1. Вы можете делать с приоритетами все, что захотите, не влияя на правильность - это все еще двоичное дерево поиска под всем этим. Можно (но более сложно) повторить анализ времени выполнения, чтобы обработать небольшую вероятность коллизий приоритетов, не жертвуя асимптотической границей O(log n).

2. Вот как может выглядеть оператор сравнения в Python. Первоначально приоритеты []Пустой список и биты заполняются лениво, как описано. Я использую списки битов; для большей эффективности было бы целесообразно упаковать их в более крупные целочисленные типы.

   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