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  +  , 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...

Full description

Saved in:
Bibliographic Details
Published in:PeerJ. Computer science 2021, Vol.7, p.e483-e483, Article e483
Main Authors: Kreitzberg, Patrick, Lucke, Kyle, Pennington, Jake, Serang, Oliver
Format: Article
Language:English
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2376-5992
2376-5992
DOI:10.7717/peerj-cs.483