2

在我在网上看到的大多数示例中，都认为有某种外部随机数生成器会产生随机（不同的！）优先级。

据我回忆，有一种方法可以实际随机生成优先级，并且在将它们插入到treap 中以解开可能的优先级冲突时。

那我有两个问题：

  1. treaps 是否真的需要使其优先级完全不同，或者只需要比较可能最终被比较的节点的优先级？也就是说，如果我有两个具有优先级的节点，p但我可以确保它们永远不会以任何方式相遇，那么让它们具有相同的优先级会有问题吗？
  2. 我应该如何在我的陷阱中生成和解开优先级？

谢谢

编辑：这是我在说什么的描述：

问题 8.12 @随机算法

现在让我们分析实现一个trap操作所需的随机位数。假设我们从单位区间 [0,1] 中均匀地随机选取每个优先级 Pi。然后，每个 Pi 的二进制表示可以生成为（可能是无限的）位序列，这些位序列是无偏掷硬币的结果。这个想法是在这个序列中只生成与解决不同优先级之间的比较所需的一样多的位。假设我们只生成了treap T 中元素优先级的二进制表示的一些前缀。现在，在插入项目y 时，我们将其优先级Py 与其他优先级进行比较以确定y 应该如何旋转。在将 Py 与一些 PI 进行比较时。如果他们当前的部分二进制表示可以解决比较，那么我们就完成了。否则。它们具有相同的部分二进制表示，我们不断为每个生成更多位，直到它们首先不同。

4

2 回答 2

1

  1. 优先级可能相同。这样做不是最理想的，因此首选低冲突随机数生成器，但检查它比仅仅接受随机的冲突机会要慢。

  2. 当一个键第一次插入到树中时，它会被分配一个优先级。为了保留treap 的结构，您将确保树在每次操作后在优先级上保持堆排序。也就是说，在每次操作之后，您要确保每个节点的优先级大于或等于其子节点的优先级。

于 2015-04-28T03:04:43.050 回答
1

  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
于 2015-04-28T03:44:58.713 回答