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)

---