An Efficient Method for Weighted Sampling without Replacement

In this note, an efficient method for weighted sampling of K objects without replacement from a population of n objects is proposed. The method requires O(Klog n) additions and comparisons, and $O(K)$ multiplications and random number generations while the method proposed by Fagin and Price requires $O(Kn)$ additions and comparisons, and $O(K)$ divisions and random number generations.