论文标题
最佳从$ x+y $中选择顶部订购堆的顶部$ k $值
Optimally selecting the top $k$ values from $X+Y$ with layer-ordered heaps
论文作者
论文摘要
选择和排序笛卡尔总和$ x+y $是经典而重要的问题。在这里，提出了一种新的算法，该算法生成了$ x_i+y_j $的顶部$ k $值。该算法仅依赖于中位数，并且易于实施。此外，它在内存中使用数据结构连续，并且在实践中是快速的。所呈现的算法在理论上是最佳的。
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.
