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 Xi+Yj . The algorithm relies on layer-ordered heaps, partial orderings of exponentially sized layers. The algorithm relies only on median-of-medians and is simple to implement. Furthermore, it uses data structures contiguous in memory, cache efficient, and fast in practice. The presented algorithm is demonstrated to be theoretically optimal.

Keywords

• Selection
• Cartesian product
• Sorting
• Combinatorics