Selection from Heaps, Row-Sorted Matrices, and X+Y Using Soft Heaps.

Haim Kaplan, Lszl Kozma, Or Zamir, Uri Zwick

Browse the full SODA paper archive.