如何高效实现带最大权重元素的随机抽取及动态维护？

存在一个权重数组w，权重为整数，已知其最小和最大值，不同权重的数量可能较多。

示例权重数组：

+----------+----+----+----+----+----+
| Weights  | 20 | 20 | 50 | 50 | 60 |
+----------+----+----+----+----+----+
| Index    |  0 |  1 |  2 |  3 |  4 |
+----------+----+----+----+----+----+

另有集合S，元素为该数组的索引：

+----------+----+----+----+
| Weights  | 50 | 50 | 20 |
+----------+----+----+----+
| S        |  2 |  3 |  1 |
+----------+----+----+----+

设M为S中索引对应的最大权重，此例中M=50，对应索引2和3。

需求：能够随机选择（并删除）S中带最大权重的元素（此例中以50%概率选2或3），同时支持在操作间隙对S进行索引的增删，目标是设计高效支持所有操作的数据结构。

当前解决方案 #

将S中带最大权重的元素（此例为2、3）存储在数组L中，为支持O(1)删除，配套数组Lptrs，ptrs[i]表示i在L中的索引，不在L中则为-1。
将S中其余元素（此例为1）存入最大堆H，同样配套数组Hptrs，支持O(1)查找索引在堆中的位置。

随机抽取最大权重索引 #

直接从L中随机选取一个索引，时间复杂度O(1)

向S中插入新索引i #

• 一般情况：若w[i] < M，则将i插入堆H，时间复杂度O(log(|H|))
• 理想情况：若w[i] == M，则将i插入数组L，时间复杂度O(1)
• 最坏情况：若w[i] > M，则更新M，将L中所有元素逐个插入H，L仅保留i

从S中删除索引i #

• 一般情况：若w[i] < M，则通过Hptrs在O(1)时间定位i，从H中删除的时间复杂度O(log(|H|))
• 理想情况：若w[i] == M且L的大小≥2，则通过Lptrs在*O(1)*时间定位并删除i
• 最坏情况：若w[i] == M且L的大小为1，则*O(1)*时间定位并删除i，随后将M更新为堆H根节点的权重，将H中所有带权重M的索引取出并插入L

内容的提问来源于stack exchange，提问作者user29618010