{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T03:35:49Z","timestamp":1760240149365,"version":"build-2065373602"},"reference-count":42,"publisher":"MDPI AG","issue":"3","license":[{"start":{"date-parts":[[2019,3,6]],"date-time":"2019-03-06T00:00:00Z","timestamp":1551830400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>We study the selection problem, namely that of computing the ith order statistic of n given elements. Here we offer a data structure called selectable sloppy heap that handles a dynamic version in which upon request (i) a new element is inserted or (ii) an element of a prescribed quantile group is deleted from the data structure. Each operation is executed in constant time\u2014and is thus independent of n (the number of elements stored in the data structure)\u2014provided that the number of quantile groups is fixed. This is the first result of this kind accommodating both insertion and deletion in constant time. As such, our data structure outperforms the soft heap data structure of Chazelle (which only offers constant amortized complexity for a fixed error rate     0 &lt; \u03b5 \u2264 1 \/ 2    ) in applications such as dynamic percentile maintenance. The design demonstrates how slowing down a certain computation can speed up the data structure. The method described here is likely to have further impact in the field of data structure design in extending asymptotic amortized upper bounds to same formula asymptotic worst-case bounds.<\/jats:p>","DOI":"10.3390\/a12030058","type":"journal-article","created":{"date-parts":[[2019,3,7]],"date-time":"2019-03-07T10:52:22Z","timestamp":1551955942000},"page":"58","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["A Selectable Sloppy Heap"],"prefix":"10.3390","volume":"12","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1118-0321","authenticated-orcid":false,"given":"Adrian","family":"Dumitrescu","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Wisconsin\u2014Milwaukee, Milwaukee, WI 53201, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2019,3,6]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"448","DOI":"10.1016\/S0022-0000(73)80033-9","article-title":"Time bounds for selection","volume":"7","author":"Blum","year":"1973","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1145\/360680.360691","article-title":"Expected time bounds for selection","volume":"18","author":"Floyd","year":"1975","journal-title":"Commun. ACM"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1137\/0205010","article-title":"Bounds for selection","volume":"5","author":"Hyafil","year":"1976","journal-title":"SIAM J. Comput."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"184","DOI":"10.1016\/S0022-0000(76)80029-3","article-title":"Finding the median","volume":"13","author":"Paterson","year":"1976","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"501","DOI":"10.1145\/360336.360339","article-title":"New upper bounds for selection","volume":"19","author":"Yap","year":"1976","journal-title":"Commun. ACM"},{"key":"ref_6","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., and Stein, C. (2009). Introduction to Algorithms, MIT Press. [3rd ed.]."},{"key":"ref_7","unstructured":"Kleinberg, J., and Tardos, \u00c9. (2006). Algorithm Design, Pearson & Addison\u2013Wesley."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Mitzenmacher, M., and Upfal, E. (2005). Probability and Computing: Randomized Algorithms and Probabilistic Analysis, Cambridge University Press.","DOI":"10.1017\/CBO9780511813603"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Chen, K., and Dumitrescu, A. (2015, January 5\u20137). Select with groups of 3 or 4. Proceedings of the 14th International Symposium on Algorithms and Data Structures (WADS 2015), Victoria, BC, Canada.","DOI":"10.1007\/978-3-319-21840-3_16"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1016\/0022-0000(89)90035-4","article-title":"Optimal parallel selection has complexity O(log logn)","volume":"38","author":"Ajtai","year":"1989","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Battiato, S., Cantone, D., Catalano, D., Cincotti, G., and Hofri, M. (2000, January 1\u20133). An efficient algorithm for the approximate median selection problem. Proceedings of the 4th Italian Conference on Algorithms and Complexity (CIAC 2000), Rome, Italy.","DOI":"10.1007\/3-540-46521-9_19"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Bent, S.W., and John, J.W. (1985, January 6\u20138). Finding the median requires 2n comparisons. Proceedings of the 17th Annual ACM Symposium on Theory of Computing (STOC 1985), Providence, RI, USA.","DOI":"10.1145\/22145.22169"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"270","DOI":"10.1145\/62044.62047","article-title":"Average case selection","volume":"36","author":"Cunto","year":"1989","journal-title":"J. ACM"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1137\/S0895480196309481","article-title":"On lower bounds for selecting the median","volume":"14","author":"Dor","year":"2001","journal-title":"SIAM J. Discret. Math."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1007\/BF01300126","article-title":"Finding the \u03b1nth largest element","volume":"16","author":"Dor","year":"1996","journal-title":"Combinatorica"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"1722","DOI":"10.1137\/S0097539795288611","article-title":"Selecting the median","volume":"28","author":"Dor","year":"1999","journal-title":"SIAM J. Comput."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1145\/322123.322128","article-title":"A counting approach to lower bounds for selection problems","volume":"26","author":"Fussenegger","year":"1979","journal-title":"J. ACM"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1145\/235767.235772","article-title":"Finding the ith largest of n for small i,n","volume":"27","author":"Gasarch","year":"1996","journal-title":"SIGACT News"},{"key":"ref_19","first-page":"585","article-title":"Selecting the t-th largest using binary errorless comparisons","volume":"4","author":"Hadian","year":"1969","journal-title":"Comb. Theory Its Appl."},{"key":"ref_20","first-page":"321","article-title":"Algorithm 63 (PARTITION) and algorithm 65 (FIND)","volume":"4","author":"Hoare","year":"1961","journal-title":"Commun. ACM"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"640","DOI":"10.1137\/0217040","article-title":"A new lower bound for the set-partitioning problem","volume":"17","author":"John","year":"1988","journal-title":"SIAM J. Comput."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"150","DOI":"10.1145\/322234.322245","article-title":"A unified lower bound for selection and set partitioning problems","volume":"28","author":"Kirkpatrick","year":"1981","journal-title":"J. ACM"},{"key":"ref_23","unstructured":"Paterson, M. (1996, January 3\u20135). Progress in selection. Proceedings of the 5th Scandinavian Workshop on Algorithm Theory (SWAT 1996), Reykjav\u00edk, Iceland."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"428","DOI":"10.1137\/0211034","article-title":"On the average-case complexity of selecting the kth best","volume":"11","author":"Yao","year":"1982","journal-title":"SIAM J. Comput."},{"key":"ref_25","unstructured":"Yao, F. (1974). On Lower Bounds for Selection Problems, Technical Report MAC TR-121, Massachusetts Institute of Technology."},{"key":"ref_26","unstructured":"Knuth, D.E. (1998). The Art of Computer Programming, Vol. 3: Sorting and Searching, Addison\u2013Wesley. [2nd ed.]."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1145\/2444016.2493373","article-title":"Optimal selection and sorting via dynamic programming","volume":"18","author":"Hofri","year":"2013","journal-title":"ACM J. Exp. Algorithmics"},{"key":"ref_28","unstructured":"Baase, S. (1988). Computer Algorithms: Introduction to Design and Analysis, Addison-Wesley. [2nd ed.]."},{"key":"ref_29","unstructured":"Dasgupta, S., Papadimitriou, C., and Vazirani, U. (2008). Algorithms, Mc Graw Hill."},{"key":"ref_30","unstructured":"Aho, A.V., Hopcroft, J.E., and Ullman, J.D. (1983). Data Structures and Algorithms, Addison\u2013Wesley."},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Jayapaul, V., Munro, J.I., Raman, V., and Satti, S.R. (2015, January 5\u20137). Sorting and selection with equality comparisons. Proceedings of the 14th International Symposium on Algorithms and Data Structures, Victoria, BC, Canada.","DOI":"10.1007\/978-3-319-21840-3_36"},{"key":"ref_32","first-page":"61","article-title":"Closing a long-standing complexity gap for selection: V3(42) = 50","volume":"Volume 8066","author":"Brodnik","year":"2013","journal-title":"Space-Efficient Data Structures, Streams, and Algorithms\u2014Papers in Honor of J. Ian Munro on the Occasion of His 66th Birthday"},{"key":"ref_33","unstructured":"Alexandrescu, A. (2017, January 21\u201323). Fast deterministic selection. Proceedings of the 16th International Symposium on Experimental Algorithms (SEA 2017), London, UK."},{"key":"ref_34","first-page":"27","article-title":"Quake heaps: A simple alternative to Fibonacci heaps","volume":"Volume 8066","author":"Brodnik","year":"2013","journal-title":"Space-Efficient Data Structures, Streams, and Algorithms\u2014Papers in Honor of J. Ian Munro on the Occasion of His 66th Birthday"},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"1012","DOI":"10.1145\/355541.355554","article-title":"The soft heap: An approximate priority queue with optimal error rate","volume":"47","author":"Chazelle","year":"2000","journal-title":"J. ACM"},{"key":"ref_36","unstructured":"Fredman, M. Personal communication."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"200","DOI":"10.1145\/7531.7537","article-title":"Slowing down sorting networks to obtain faster sorting algorithms","volume":"34","author":"Cole","year":"1987","journal-title":"J. ACM"},{"key":"ref_38","unstructured":"Fredman, M. (arXiv, 2016). Comments on Dumitrescu\u2019s \u201cA Selectable Sloppy Heap\u201d, arXiv."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"124","DOI":"10.1007\/BFb0038186","article-title":"Sorting, measures of disorder, and worst-case performance","volume":"Volume 555","author":"Maurer","year":"1991","journal-title":"New Results and New Trends in Computer Science"},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"318","DOI":"10.1109\/TC.1985.5009382","article-title":"Measures of presortedness and optimal sorting algorithms","volume":"34","author":"Manilla","year":"1985","journal-title":"IEEE Trans. Comput."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"1028","DOI":"10.1145\/355541.355562","article-title":"A minimum spanning tree algorithm with inverse-Ackermann type complexity","volume":"47","author":"Chazelle","year":"2000","journal-title":"J. ACM"},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1145\/201019.201022","article-title":"A Randomized linear-time algorithm to find minimum spanning trees","volume":"42","author":"Karger","year":"1995","journal-title":"J. ACM"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/12\/3\/58\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T12:36:42Z","timestamp":1760186202000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/12\/3\/58"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,3,6]]},"references-count":42,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2019,3]]}},"alternative-id":["a12030058"],"URL":"https:\/\/doi.org\/10.3390\/a12030058","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2019,3,6]]}}}