Suppose I want to randomly sample from a large set of items, each of which has a "score". I want my probability of sampling to be proportional to the score. One simple way to achieve this is divide each score by the total, then randomly sample based on each probability. This is at least O(N), and running it the next time will be O(N) as well since we have to renormalize. Inserting is also O(N) because we have to renormalize. I'm wondering if there is way we can utilize a priority queue or binary tree to make sampling and insertion less costly.
I am thinking for example, store every item in a priority queue, then to sample: Look at the current item's score, the left item's sum of scores, and the right item's sum of scores. Normalize by dividing each by the sum of all three, and sample the result. If the result is the left, rerun the algorithm on the left node. If the result is the right, rerun the algorithm on the right node. Otherwise if it's the current node, remove the node and return it as the sample. It is guaranteed to terminate when it gets to a leaf. We would have to do some extra work to keep track of the sum, but I think this would make all operations O(log(N)). Not sure this would sample with the actual required probability or if the time complexity is correct. Is there any existing work on this?
Edit: I think I found the answer: https://en.wikipedia.org/wiki/Reservoir_sampling#Algorithm_A-Res
