Is there an algorithm for random sampling from a priority queue with probability proportional to priority? Suppose I want to randomly sample from a large set of items, each of which has a &quot;score&quot;.  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
This is exactly what the A-Res algorithm is for
If you have a positive weight for each sample, then you can achieve a probability of sampling proportional to the weight, even without knowing all of the other weights at a given time.  The way you achieve this is:

For each sample: randomly generate a number between from 0 to 1
Raise the result to the power of (1/weight).

It can be shown that a sample with N times the weight of another sample is N times more likely to be greater (have higher priority)