实现随机删除和插入的数据结构，其中元素在[a,b]中加权
Data structure to achieve random delete and insert where elements are weighted in [a,b]
我想设计一个数据结构和算法，这样，给定一个元素数组，其中每个元素都有一个根据 [a,b] 的权重，我可以实现 constant 时间插入和删除。删除是随机进行的，元素被删除的概率与其权重成正比。
我不相信有确定性算法可以在恒定时间内实现这两个操作，但我认为应该有随机算法可以做到这一点？
我不知道O(1) 最坏情况时间是否不可能；我看不出有什么特别的理由。但是绝对有可能有一个简单的数据结构来实现 O(1) 的预期时间。
想法是存储一个dynamic array of pairs (or two parallel arrays)，其中每个项目都与其权重配对；插入是通过在 O(1) 分摊时间中附加来完成的，并且可以通过将元素与最后一个元素交换来按索引删除元素，以便可以在 O(1) 时间内将其从数组末尾删除。从加权分布中抽取一个随机元素，选择一个随机指标，生成一个半开区间[0, 2)内的随机数；如果它小于元素的权重，则 select 该索引处的元素，否则重复此过程直到元素被 selected。这个想法是每个索引被选择的可能性是相等的，它被保留而不是被拒绝的概率与其权重成正比。
这是一个Las Vegas algorithm, meaning it is expected to complete in a finite time, but with very low probability it can take arbitrarily long to complete. The number of iterations required to sample an element will be highest when every weight is exactly 1, in which case it follows a geometric distribution，参数p = 1/2，所以它的期望值为2，一个与数据结构中元素数量无关的常量。
一般来说，如果所有的权重都在区间[a, b]对于实数0 < a <= b，那么期望的迭代次数最多为b/a。这始终是一个常数，但如果下限 a 相对于 b.
这本身并不是一个答案，而只是一个小例子来说明@kaya3
设计的算法
| value | weight |
| v1 | 1.0 |
| v2 | 1.5 |
| v3 | 1.5 |
| v4 | 2.0 |
| v5 | 1.0 |
| total | 7.0 |
总重量为7.0。通过将它存储在一些内存中并且在每个 insertion/removal.
处存储 increasing/decreasing 很容易在 O(1) 中维护
每个元素的概率就是它的权重除以总权重。
| value | proba |
| v1 | 1.0/7 | 0.1428...
| v2 | 1.5/7 | 0.2142...
| v3 | 1.5/7 | 0.2142...
| v4 | 2.0/7 | 0.2857...
| v5 | 1.0/7 | 0.1428...
使用@kaya3的算法，如果我们抽取一个随机索引，那么每个值的概率都是1/size（这里是1/5）。
v1 被拒绝的几率为 50%，v2 为 25%，v4 为 0%。所以第一轮被选中的概率是：
| value | proba |
| v1 | 2/20 | 0.10
| v2 | 3/20 | 0.15
| v3 | 3/20 | 0.15
| v4 | 4/20 | 0.20
| v5 | 2/20 | 0.10
| total | 14/20 | (70%)
那么第2轮的概率是30%，每个指标的概率是6/20/5 = 3/50
| value | proba 2 rounds |
| v1 | 2/20 + 6/200 | 0.130
| v2 | 3/20 + 9/200 | 0.195
| v3 | 3/20 + 9/200 | 0.195
| v4 | 4/20 + 12/200 | 0.260
| v5 | 2/20 + 6/200 | 0.130
| total | 14/20 + 42/200 | (91%)
进入第 3 轮的概率为 9%，即每个指数为 9/500
| value | proba 3 rounds |
| v1 | 2/20 + 6/200 + 18/2000 | 0.1390
| v2 | 3/20 + 9/200 + 27/2000 | 0.2085
| v3 | 3/20 + 9/200 + 27/2000 | 0.2085
| v4 | 4/20 + 12/200 + 36/2000 | 0.2780
| v5 | 2/20 + 6/200 + 18/2000 | 0.1390
| total | 14/20 + 42/200 + 126/2000 | (97,3%)
所以我们看到系列收敛到正确的概率。分子是权重的倍数，所以很明显每个元素的相对权重都得到了尊重。
这是一个答案的草图。
权重只有 1，我们可以保持输入的随机排列。
每次插入一个元素，将其放在数组的末尾，然后在数组中随机选择一个位置i，将最后一个元素与位置i的元素交换。
（如果随机位置是最后一个，则很可能是空操作。）
删除时，只删除最后一个元素。
假设我们可以使用具有 O(1)（最坏情况或摊销）插入和删除的动态数组，这会在 O(1) 中进行插入和删除。
对于权重1和2，可以使用类似的结构。
也许权重为 2 的每个元素都应该放两次而不是一次。
也许当一个权重为 2 的元素被删除时，它的另一个副本也应该被删除。
所以我们实际上应该存储索引而不是元素，以及另一个数组 locations，它存储和跟踪每个元素的两个索引。交换应该使这个 locations 数组保持最新。
删除任意元素可以在 O(1) 中完成，类似于插入：与最后一个交换，删除最后一个。
我想设计一个数据结构和算法，这样，给定一个元素数组，其中每个元素都有一个根据 [a,b] 的权重，我可以实现 constant 时间插入和删除。删除是随机进行的，元素被删除的概率与其权重成正比。
我不相信有确定性算法可以在恒定时间内实现这两个操作，但我认为应该有随机算法可以做到这一点？
我不知道O(1) 最坏情况时间是否不可能；我看不出有什么特别的理由。但是绝对有可能有一个简单的数据结构来实现 O(1) 的预期时间。
想法是存储一个dynamic array of pairs (or two parallel arrays)，其中每个项目都与其权重配对；插入是通过在 O(1) 分摊时间中附加来完成的，并且可以通过将元素与最后一个元素交换来按索引删除元素，以便可以在 O(1) 时间内将其从数组末尾删除。从加权分布中抽取一个随机元素，选择一个随机指标，生成一个半开区间[0, 2)内的随机数；如果它小于元素的权重，则 select 该索引处的元素，否则重复此过程直到元素被 selected。这个想法是每个索引被选择的可能性是相等的，它被保留而不是被拒绝的概率与其权重成正比。
这是一个Las Vegas algorithm, meaning it is expected to complete in a finite time, but with very low probability it can take arbitrarily long to complete. The number of iterations required to sample an element will be highest when every weight is exactly 1, in which case it follows a geometric distribution，参数p = 1/2，所以它的期望值为2，一个与数据结构中元素数量无关的常量。
一般来说，如果所有的权重都在区间[a, b]对于实数0 < a <= b，那么期望的迭代次数最多为b/a。这始终是一个常数，但如果下限 a 相对于 b.
这本身并不是一个答案，而只是一个小例子来说明@kaya3
设计的算法| value | weight |
| v1 | 1.0 |
| v2 | 1.5 |
| v3 | 1.5 |
| v4 | 2.0 |
| v5 | 1.0 |
| total | 7.0 |
总重量为7.0。通过将它存储在一些内存中并且在每个 insertion/removal.
处存储 increasing/decreasing 很容易在 O(1) 中维护每个元素的概率就是它的权重除以总权重。
| value | proba |
| v1 | 1.0/7 | 0.1428...
| v2 | 1.5/7 | 0.2142...
| v3 | 1.5/7 | 0.2142...
| v4 | 2.0/7 | 0.2857...
| v5 | 1.0/7 | 0.1428...
使用@kaya3的算法，如果我们抽取一个随机索引，那么每个值的概率都是1/size（这里是1/5）。
v1 被拒绝的几率为 50%，v2 为 25%，v4 为 0%。所以第一轮被选中的概率是：
| value | proba |
| v1 | 2/20 | 0.10
| v2 | 3/20 | 0.15
| v3 | 3/20 | 0.15
| v4 | 4/20 | 0.20
| v5 | 2/20 | 0.10
| total | 14/20 | (70%)
那么第2轮的概率是30%，每个指标的概率是6/20/5 = 3/50
| value | proba 2 rounds |
| v1 | 2/20 + 6/200 | 0.130
| v2 | 3/20 + 9/200 | 0.195
| v3 | 3/20 + 9/200 | 0.195
| v4 | 4/20 + 12/200 | 0.260
| v5 | 2/20 + 6/200 | 0.130
| total | 14/20 + 42/200 | (91%)
进入第 3 轮的概率为 9%，即每个指数为 9/500
| value | proba 3 rounds |
| v1 | 2/20 + 6/200 + 18/2000 | 0.1390
| v2 | 3/20 + 9/200 + 27/2000 | 0.2085
| v3 | 3/20 + 9/200 + 27/2000 | 0.2085
| v4 | 4/20 + 12/200 + 36/2000 | 0.2780
| v5 | 2/20 + 6/200 + 18/2000 | 0.1390
| total | 14/20 + 42/200 + 126/2000 | (97,3%)
所以我们看到系列收敛到正确的概率。分子是权重的倍数，所以很明显每个元素的相对权重都得到了尊重。
这是一个答案的草图。
权重只有 1，我们可以保持输入的随机排列。
每次插入一个元素，将其放在数组的末尾，然后在数组中随机选择一个位置i，将最后一个元素与位置i的元素交换。
（如果随机位置是最后一个，则很可能是空操作。）
删除时，只删除最后一个元素。
假设我们可以使用具有 O(1)（最坏情况或摊销）插入和删除的动态数组，这会在 O(1) 中进行插入和删除。
对于权重1和2，可以使用类似的结构。
也许权重为 2 的每个元素都应该放两次而不是一次。
也许当一个权重为 2 的元素被删除时，它的另一个副本也应该被删除。
所以我们实际上应该存储索引而不是元素，以及另一个数组 locations，它存储和跟踪每个元素的两个索引。交换应该使这个 locations 数组保持最新。
删除任意元素可以在 O(1) 中完成，类似于插入：与最后一个交换，删除最后一个。