Name
Abstract | ||
|---|---|---|
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 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. |
Year | Venue | DocType |
|---|---|---|
2019 | SOSA@SODA | Conference |
Volume | Citations | PageRank |
abs/1802.07041 | 0 | 0.34 |
References | Authors | |
9 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Haim Kaplan | 1 | 3581 | 263.96 |
| László Kozma | 2 | 41 | 7.58 |
| Or Zamir | 3 | 9 | 2.20 |
| Uri Zwick | 4 | 3586 | 257.02 |