Fast sampling and update of weighted items? (data structure like red-black trees?)
jonnyba: if the number of different weights is finite and small, you could create a bucket for each different weight.for example if the possible weights are .25, .5, and .75, put all items into one of those buckets (array backed).  The bucket then gets a weight of (individual weight)*(bucket size).  First randomly choose a bucket based on the bucket weight, then randomly choose an object from the bucket.