We use soft heaps to obtain simpler optimal algorithms for selecting the k-th smallest item and the set of k smallest items, from a heap-ordered tree, from a collection of sorted lists, and from X + Y, where X and Y are two unsorted sets. Our results match, and in some ways extend and improve, classical results of Frederickson (1993) and Frederickson and Johnson (1982).
Joint work with Haim Kaplan, Or Zamir, and Uri Zwick.