License
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.SOSA.2019.5
URN: urn:nbn:de:0030-drops-100315
URL: http://drops.dagstuhl.de/opus/volltexte/2018/10031/
Go to the corresponding OASIcs Volume Portal


Kaplan, Haim ; Kozma, László ; Zamir, Or ; Zwick, Uri

Selection from Heaps, Row-Sorted Matrices, and X+Y Using Soft Heaps

pdf-format:
OASIcs-SOSA-2019-5.pdf (0.7 MB)


Abstract

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.

BibTeX - Entry

@InProceedings{kaplan_et_al:OASIcs:2018:10031,
  author =	{Haim Kaplan and L{\'a}szl{\'o} Kozma and Or Zamir and Uri Zwick},
  title =	{{Selection from Heaps, Row-Sorted Matrices, and X+Y Using Soft Heaps}},
  booktitle =	{2nd Symposium on Simplicity in Algorithms (SOSA 2019)},
  pages =	{5:1--5:21},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-099-6},
  ISSN =	{2190-6807},
  year =	{2018},
  volume =	{69},
  editor =	{Jeremy T. Fineman and Michael Mitzenmacher},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/10031},
  URN =		{urn:nbn:de:0030-drops-100315},
  doi =		{10.4230/OASIcs.SOSA.2019.5},
  annote =	{Keywords: selection, soft heap}
}

Keywords: selection, soft heap
Seminar: 2nd Symposium on Simplicity in Algorithms (SOSA 2019)
Issue Date: 2018
Date of publication: 18.12.2018


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI