Fast sampling and update of weighted items? (data structure like red-black trees?)
mjtokelly: Here's a sampling algorithm that will work, as long as the maximum weight isn't too much greater than the average weight:1) Determine the maximum weight mw.  (This is O(N) the first time, O(K) subsequent times.)2) Repeat until an index i is accepted:  a) Generate a random pair (i, x), where i is a uniform integer over [1,N], and x is a uniform float over [0,mw].

  b) Accept index i if weight(i) < x.

3) Return the accepted index i.This gives you the desired distribution in time O(mw/aw) (maximum weight over average weight).