Selection on X(1) + X(2) + ⋯ + X(m) via Cartesian product trees

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.