c# - Weighted Random Selection from a Sorted List -

i have problem in have large list of items sorted "weights". need able randomly select items list, items closer start (greater weights) must have greater chance of being selected based on "elitism" factor.

i realize similar questions have been asked before, catch here list changing on time. new values sorted list last item deleted (to keep constant sized pool of "optimized" values).

first off, efficient way of doing selection? selection must happen in real time list anywhere 50 1000 item long.

second, best data structure use here? i'm using c#. thanks!

i thought of possible solution, i'd feedback on idea. if generate random float value within range, , along lines of squaring it? small values return small values, , large values return larger values. can tell, mapping result length of list should give desired effect. sound right?

create binary tree, sorted weight (sorting not required except it's specified in question), , each node record total weight of children. @ top of can calculate total weight of whole list.

pick random value r between 0 , total weight of everything. @ each node, if weight of current node greater r result. otherwise subtract weight of current node r. now, if total weight of left children less r go left. otherwise subtract total weight of left children r , go right. repeat until have result.

insertion , deletion costs down how choose implement , balance tree, have traverse ancestors update weights.

if don't need sorted making heap might improve fast-out behaviour.