Kreitzberg Patrick, Lucke Kyle, Pennington Jake, Serang Oliver
Department of Mathematics, University of Montana, Missoula, MT, United States of America.
Department of Computer Science, University of Montana, Missoula, MT, United States of America.
PeerJ Comput Sci. 2021 Apr 28;7:e483. doi: 10.7717/peerj-cs.483. eCollection 2021.
Selection on the Cartesian product is a classic problem in computer science. Recently, an optimal algorithm for selection on + , based on soft heaps, was introduced. By combining this approach with layer-ordered heaps (LOHs), an algorithm using a balanced binary tree of + selections was proposed to perform selection on + + ⋯ + in (⋅ + ⋅), where have length . Here, that (⋅ + ⋅) algorithm is combined with a novel, optimal LOH-based algorithm for selection on + (without a soft heap). Performance of algorithms for selection on + + ⋯ + are compared empirically, demonstrating the benefit of the algorithm proposed here.
笛卡尔积上的选择是计算机科学中的一个经典问题。最近，引入了一种基于软堆的针对 + 上选择的最优算法。通过将这种方法与层序堆（LOH）相结合，提出了一种使用 + 选择的平衡二叉树的算法，以在 (⋅ + ⋅) 的时间内对 + + ⋯ + 进行选择，其中 的长度为 。在这里，将那种 (⋅ + ⋅) 算法与一种新颖的、基于 LOH 的针对 + 选择的最优算法（不使用软堆）相结合。通过实验比较了对 + + ⋯ + 进行选择的算法的性能，证明了这里提出的算法的优势。
