Selection on X ₁ + X ₂ + ⋯ + X 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 ₁ + X ₂ + ⋯ + X in o(n⋅m + k⋅m), where X 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 ₁ + X ₂ + ⋯ + X are compared empirically, demonstrating the benefit of the algorithm proposed here.