论文标题
$ x_1 + x_1 + \ cdots x_m $通过笛卡尔产品树进行选择
Selection on $X_1 + X_1 + \cdots X_m$ via Cartesian product tree
论文作者
论文摘要
在笛卡尔产品上的选择是计算机科学中的经典问题。最近，引入了一种基于软堆的$ x+y $选择的最佳算法。通过将这种方法与图层订购的堆（LOHS）相结合，建议使用$ x+y $选择的算法使用$ x_1+x_1+x_2+x_2+\ cdots+x_m $ in $ o（n \ cdot m+k \ cdot m）$ x_1+x_m $ in $ x+x_2+x_m $，其中$ k $ $ x_i $ x_i $ x_i $ x_i $ x_i $ x_i $。在这里，该$ O（N \ CDOT M + K \ CDOT M）$算法与一种基于$ x + y $的新颖，最佳的基于LOH的算法（无软堆）结合使用。在$ x_1+x_2+\ cdots+x_m $上进行选择的算法的性能是经验比较的，这证明了此处提出的算法的好处。
Selection on the Cartesian product is a classic problem in computer science. Recently, an optimal algorithm for selection on $X+Y$, based on soft heaps, was introduced. By combining this approach with layer-ordered heaps (LOHs), an algorithm using a balanced binary tree of $X+Y$ selections was proposed to perform $k$-selection on $X_1+X_2+\cdots+X_m$ in $o(n\cdot m + k\cdot m)$, where $X_i$ have length $n$. Here, that $o(n\cdot m + k\cdot m)$ algorithm is combined with a novel, optimal LOH-based algorithm for selection on $X+Y$ (without a soft heap). Performance of algorithms for selection on $X_1+X_2+\cdots+X_m$ are compared empirically, demonstrating the benefit of the algorithm proposed here.
