Abstract
Selection on the Cartesian product is a classic problem in computer science. Recently, an optimal algorithm for selection on A+B, based on soft heaps, was introduced. By combining this approach with layer-ordered heaps (LOHs), an algorithm using a balanced binary tree of A+B selections was proposed to perform selection on X-1+X-2+...+X-m in o(n.m+k.m), where X-i have length n. Here, that o(n.m+k.m) algorithm is combined with a novel, optimal LOH-based algorithm for selection on A+B (without a soft heap). Performance of algorithms for selection on X-1+X-2+...+X-m are compared empirically, demonstrating the benefit of the algorithm proposed here.