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

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



PDF
Thumbnail PDF

File

OASIcs.SOSA.2019.5.pdf
  • Filesize: 0.68 MB
  • 21 pages

Document Identifiers

Author Details

Haim Kaplan
László Kozma
Or Zamir
Uri Zwick

Cite AsGet BibTex

Haim Kaplan, László Kozma, Or Zamir, and Uri Zwick. Selection from Heaps, Row-Sorted Matrices, and X+Y Using Soft Heaps. In 2nd Symposium on Simplicity in Algorithms (SOSA 2019). Open Access Series in Informatics (OASIcs), Volume 69, pp. 5:1-5:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/OASIcs.SOSA.2019.5

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.
Keywords
  • selection
  • soft heap

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Manuel Blum, Robert W. Floyd, Vaughan R. Pratt, Ronald L. Rivest, and Robert Endre Tarjan. Time Bounds for Selection. J. Comput. Syst. Sci., 7(4):448-461, 1973. URL: http://dx.doi.org/10.1016/S0022-0000(73)80033-9.
  2. David Bremner, Timothy M. Chan, Erik D. Demaine, Jeff Erickson, Ferran Hurtado, John Iacono, Stefan Langerman, Mihai Patrascu, and Perouz Taslakian. Necklaces, Convolutions, and X+Y. Algorithmica, 69(2):294-314, 2014. URL: http://dx.doi.org/10.1007/s00453-012-9734-3.
  3. Gerth Stølting Brodal, Rolf Fagerberg, Mark Greve, and Alejandro López-Ortiz. Online Sorted Range Reporting. In Proc. of 20th ISAAC, pages 173-182, 2009. URL: http://dx.doi.org/10.1007/978-3-642-10631-6_19.
  4. Jean Cardinal, Samuel Fiorini, Gwenaël Joret, Raphaël M. Jungers, and J. Ian Munro. Sorting under partial information (without the ellipsoid algorithm). Combinatorica, 33(6):655-697, 2013. URL: http://dx.doi.org/10.1007/s00493-013-2821-5.
  5. Bernard Chazelle. A minimum spanning tree algorithm with Inverse-Ackermann type complexity. J. ACM, 47(6):1028-1047, 2000. URL: http://dx.doi.org/10.1145/355541.355562.
  6. Bernard Chazelle. The soft heap: an approximate priority queue with optimal error rate. J. ACM, 47(6):1012-1027, 2000. URL: http://dx.doi.org/10.1145/355541.355554.
  7. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, 3rd Edition. MIT Press, 2009. URL: http://mitpress.mit.edu/books/introduction-algorithms.
  8. Dorit Dor and Uri Zwick. Selecting the Median. SIAM Journal on Computing, 28(5):1722-1758, 1999. URL: http://dx.doi.org/10.1137/S0097539795288611.
  9. Dorit Dor and Uri Zwick. Median Selection Requires (2+ε)n Comparisons. SIAM Journal on Discrete Mathematics, 14(3):312-325, 2001. URL: http://dx.doi.org/10.1137/S0895480199353895.
  10. David Eppstein. Finding the k Shortest Paths. SIAM J. Comput., 28(2):652-673, 1998. URL: http://dx.doi.org/10.1137/S0097539795290477.
  11. Greg N. Frederickson. An Optimal Algorithm for Selection in a Min-Heap. Information and Computation, 104(2):197-214, 1993. URL: http://dx.doi.org/10.1006/inco.1993.1030.
  12. Greg N. Frederickson and Donald B. Johnson. The Complexity of Selection and Ranking in X+Y and Matrices with Sorted Columns. J. Comput. Syst. Sci., 24(2):197-208, 1982. URL: http://dx.doi.org/10.1016/0022-0000(82)90048-4.
  13. Greg N. Frederickson and Donald B. Johnson. Generalized Selection and Ranking: Sorted Matrices. SIAM Journal on Computing, 13(1):14-30, 1984. URL: http://dx.doi.org/10.1137/0213002.
  14. Greg N. Frederickson and Donald B. Johnson. Erratum: Generalized Selection and Ranking: Sorted Matrices. SIAM Journal on Computing, 19(1):205-206, 1990. URL: http://dx.doi.org/10.1137/0219013.
  15. Michael L. Fredman. How Good is the Information Theory Bound in Sorting? Theor. Comput. Sci., 1(4):355-361, 1976. URL: http://dx.doi.org/10.1016/0304-3975(76)90078-5.
  16. Joseph L. Hodges Jr and Erich L. Lehmann. Estimates of location based on rank tests. The Annals of Mathematical Statistics, pages 598-611, 1963. Google Scholar
  17. Donald B. Johnson and Samuel D. Kashdan. Lower Bounds for Selection in X+Y and Other Multisets. J. ACM, 25(4):556-570, 1978. URL: http://dx.doi.org/10.1145/322092.322097.
  18. Donald B. Johnson and Tetsuo Mizoguchi. Selecting the K-th element in X+Y and X₁+ X₂ + … + X_m. SIAM J. Comput., 7(2):147-153, 1978. URL: http://dx.doi.org/10.1137/0207013.
  19. Jeff Kahn and Jeong Han Kim. Entropy and Sorting. J. Comput. Syst. Sci., 51(3):390-399, 1995. URL: http://dx.doi.org/10.1006/jcss.1995.1077.
  20. Jeff Kahn and Michael Saks. Balancing poset extensions. Order, 1(2):113-126, 1984. URL: http://dx.doi.org/10.1007/BF00565647.
  21. Daniel M. Kane, Shachar Lovett, and Shay Moran. Near-optimal linear decision trees for k-SUM and related problems. In Proc. of 50th STOC, pages 554-563, 2018. URL: http://dx.doi.org/10.1145/3188745.3188770.
  22. Haim Kaplan, Robert Endre Tarjan, and Uri Zwick. Soft Heaps Simplified. SIAM Journal on Computing, 42(4):1660-1673, 2013. URL: http://dx.doi.org/10.1137/120880185.
  23. Bernard O. Koopman. The optimum distribution of effort. Journal of the Operations Research Society of America, 1(2):52-63, 1953. URL: http://dx.doi.org/10.1287/opre.1.2.52.
  24. Jean-Luc Lambert. Sorting the sums (x_i+y_j) in O(n^2) comparisons. Theoretical Computer Science, 103(1):137-141, 1992. Google Scholar
  25. Seth Pettie and Vijaya Ramachandran. An optimal minimum spanning tree algorithm. J. ACM, 49(1):16-34, 2002. URL: http://dx.doi.org/10.1145/505241.505243.
  26. Arnold Schönhage, Mike Paterson, and Nicholas Pippenger. Finding the Median. J. Comput. Syst. Sci., 13(2):184-199, 1976. URL: http://dx.doi.org/10.1016/S0022-0000(76)80029-3.
  27. William L. Steiger and Ileana Streinu. A Pseudo-Algorithmic Separation of Lines from Pseudo-Lines. Inf. Process. Lett., 53(5):295-299, 1995. URL: http://dx.doi.org/10.1016/0020-0190(94)00201-9.
  28. J.W.J. Williams. Algorithm 232: Heapsort. cacm, 7:347-348, 1964. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail