Selection from heaps, row-sorted matrices and $X+Y$ using soft heaps

Haim Kaplan, László Kozma, Or Zamir +1

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 sor…