BARC/EADS Talk by Uri Zwick

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

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). In particular, for selecting the $k$-th smallest item, or the set of~$k$ smallest items, from a collection of~$m$ sorted lists
we obtain a new optimal \emph{``output-sensitive"} algorithm that performs only $O(m+\sum_{i=1}^m \log(k_i+1))$ comparisons, where $k_i$ is the number of items of the $i$-th list that belong to the overall set of~$k$ smallest items.

Joint work with Haim Kaplan, L\'{a}szl\'{o} Kozma and Or Zamir.


Uri Zwick is professor at Tel Aviv University. He did his undergraduate studies at the Technion, Israel Institute of Technology, and his graduate studies at Tel Aviv University. After spending two post-doctoral years at Warwick University in England, he joined the faculty of Tel Aviv University in 1991.