各位好，在文章 【随机算法】蒙特卡洛 中，我们了解了蒙特卡洛方法的基本思想，实现蒙特卡洛方法最重要的是根据需求正确地实现对给定分布的随机变量的采样，并学习了直接采样。
在 【随机算法】拒绝采样 中我们学习了拒绝采样，在 【随机算法】蓄水池抽样 中我们学习了蓄水池抽样。
本文我们来看加权蓄水池抽样。我们首先给出加权蓄水池抽样的适用场景、算法流程，以及正确性证明。然后用加权蓄水池抽样解决力扣上的一道随机算法的题目，528，此外本题也可以用二分解决。
给定一个数据流 A，数据流长度 N 很大，且 N 直到处理完所有数据之前都不可知。
每个数据流中的每个数据 A[i] 有一个权重 w[i]，在处理当前数据的时候，后面数据的权重未知。
如何在只遍历一遍数据 $O(N)$ 的情况下，能够随机选取出 m 个不重复的数据。
数据流长度未知，可能很大，将全部数据读入内存的算法不可行。
随机选取 m 个数，每个数被选中的概率与其权重成正比。
当 wi 值为一般权重而非概率值时，可能会是一个很大的数值，使得求 ri 的指数操作丢失精度。
用小顶堆维护蓄水池中持有的随机数最小的哪个样本的查询，基于小顶堆的算法的时间复杂度就是 $O(mlogN)$
由于这是一个随机问题，允许多个答案，因此下列输出都可以被认为是正确的:
对加权随机事件的二分也是随机算法中比较常见的一种算法，本题就是常规的已知左右样本和权重的二分法加权采样。算法细节参考：
【随机算法】加权随机事件的二分查找。