2026-07-22T11:26:19Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10031 2024-03-06T10:30:32Z ddc:004 open_access

Selection from Heaps, Row-Sorted Matrices, and X+Y Using Soft Heaps Kaplan, Haim Kozma, László Zamir, Or Zwick, Uri selection soft heap We use soft heaps to obtain simpler optimal algorithms for selecting the k-th smallest item, and the set of k smallest items, from a heap-ordered tree, from a collection of sorted lists, and from X+Y, where X and Y are two unsorted sets. Our results match, and in some ways extend and improve, classical results of Frederickson (1993) and Frederickson and Johnson (1982). In particular, for selecting the k-th smallest item, or the set of k smallest items, from a collection of m sorted lists we obtain a new optimal "output-sensitive" algorithm that performs only O(m + sum_{i=1}^m log(k_i+1)) comparisons, where k_i is the number of items of the i-th list that belong to the overall set of k smallest items. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Haim Kaplan and László Kozma and Or Zamir and Uri Zwick 2019 Is Part Of OASIcs, Volume 69, 2nd Symposium on Simplicity in Algorithms (SOSA 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/OASIcs.SOSA.2019.5 urn:nbn:de:0030-drops-100315 https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.SOSA.2019.5 eng https://creativecommons.org/licenses/by/3.0/legalcode