Fast sampling and update of weighted items? (data structure like red-black trees?)
hotpockets: As long as the weights are distributed randomly in the array, you can just perform the algorithm on a random subsection of the array.  The subsection needs to have the same distribution of weights as the whole section.  I think thats the only requirement you need.Ideally, you could pick smaller fraction of the array as N gets bigger, giving you sub O(N) scaling.In other words, if the array indexes that get picked using a slow algorithm are distributed randomnly, you might as well just pick a random subsection, as long as it is big enough to have the same distribution of W's as the whole array.