Optimally selecting the top $k$ values from $X+Y$ with layer-ordered heaps

Abstract

Selection and sorting the Cartesian sum, $X+Y$, are classic and important problems. Here, a new algorithm is presented, which generates the top $k$ values of the form $X_i+Y_j$. The algorithm relies only on median-of-medians and is simple to implement. Furthermore, it uses data structures contiguous in memory, and is fast in practice. The presented algorithm is demonstrated to be theoretically optimal.

References in corpus (2)

• Selection on $X_1+X_2+\cdots +X_m$ with layer-ordered heaps
• Optimal construction of a layer-ordered heap

Cited by in corpus (2)

• Optimal construction of a layer-ordered heap
• Fast exact computation of the $k$ most abundant isotope peaks with layer-ordered heaps