You are not logged in |
Selection from heaps, row-sorted matrices, and X+Y, using soft heaps
- Speaker(s)
- Laszlo Kozma
- Affiliation
- Freie Universität Berlin
- Date
- Feb. 21, 2019, 12:15 p.m.
- Room
- room 5870
- Seminar
- Seminar Algorithms
We use soft heaps to obtain simpler optimal algorithms for selecting the k-th smallest item from a heap-ordered tree, from a collection of sorted lists, and from X+Y. Our results match, and in some ways extend classical results of Frederickson (1993) and Frederickson and Johnson (1982).
Joint work with Haim Kaplan, Or Zamir, Uri Zwick. (SOSA 2019)
