algorithm - 从加权列表中随机选择一个元素

Question

我有一个包含 100,000 个对象的列表。每个列表元素都有一个与之关联的“权重”，它是一个从 1 到 N 的正整数。

从列表中选择随机元素的最有效方法是什么？我想要这样的行为，即我随机选择的元素的分布与列表中的权重分布相同。

例如，如果我有一个列表 L = {1,1,2,5}，我希望平均有 5/9 的时间选择第 4 个元素。

假设插入和删除在这个列表中很常见，因此任何使用“积分区域表”的方法都需要经常更新 - 希望有一个 O(1) 运行时间和 O(1) 额外内存需求的解决方案。

Answer 1

您可以使用扩充二叉搜索树来存储元素，以及每个子树中的权重总和。这使您可以根据需要插入和删除元素和权重。采样和更新每次操作都需要 O(lg n) 时间，空间使用是 O(n)。

采样是通过在 [1, S] 中生成一个随机整数来完成的，其中 S 是所有权重的总和(S 存储在树的根部)，并使用为每个存储的权重和执行二进制搜索子树。