Weighted random selection with and without replacement
The following is a description of random weighted selection of an element of a 
set (or multiset, if repeats are allowed), both with and without replacement in O(n) space 
and O(log n) time.
It consists of implementing a binary search tree, sorted by the elements to be 
selected, where each node of the tree contains:

the element itself (element)
the un-normalized weight of the element (elementweight), and
the sum of all the un-normalized weights of the left-child node and all of 
its children (leftbranchweight).
the sum of all the un-normalized weights of the right-child node and all of
its chilren (rightbranchweight).

Then we randomly select an element from the BST by descending down the tree. A 
rough description of the algorithm follows. The algorithm is given a node of
the tree. Then the values of leftbranchweight, rightbranchweight, 
and elementweight of node is summed, and the weights are divided by this 
sum, resulting in the values leftbranchprobability, 
rightbranchprobability, and elementprobability, respectively. Then a 
random number between 0 and 1 (randomnumber) is obtained.

if the number is less than elementprobability,


remove the element from the BST as normal, updating leftbranchweight
and rightbranchweight of all the necessary nodes, and return the 
element.

else if the number is less than (elementprobability + leftbranchweight)


recurse on leftchild (run the algorithm using leftchild as node)

else 


recurse on rightchild


When we finally find, using these weights, which element is to be returned, we either simply return it (with replacement) or we remove it and update relevant weights in the tree (without replacement).
DISCLAIMER: The algorithm is rough, and a treatise on the proper implementation 
of a BST is not attempted here; rather, it is hoped that this answer will help 
those who really need fast weighted selection without replacement (like I do).
Recently I needed to do weighted random selection of elements from a list, both with and without replacement. While there are well known and good algorithms for unweighted selection, and some for weighted selection without replacement (such as modifications of the resevoir algorithm), I couldn't find any good algorithms for weighted selection with replacement. I also wanted to avoid the resevoir method, as I was selecting a significant fraction of the list, which is small enough to hold in memory.
Does anyone have any suggestions on the best approach in this situation? I have my own solutions, but I'm hoping to find something more efficient, simpler, or both.