{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,20]],"date-time":"2025-02-20T05:14:07Z","timestamp":1740028447591,"version":"3.37.3"},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540281016"},{"type":"electronic","value":"9783540317111"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11534273_6","type":"book-chapter","created":{"date-parts":[[2010,3,12]],"date-time":"2010-03-12T13:31:47Z","timestamp":1268400707000},"page":"49-60","source":"Crossref","is-referenced-by-count":5,"title":["The Complexity of Implicit and Space Efficient Priority Queues"],"prefix":"10.1007","author":[{"given":"Christian W.","family":"Mortensen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Seth","family":"Pettie","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"5","key":"6_CR1","doi-asserted-by":"publisher","first-page":"1552","DOI":"10.1137\/S0097539797329889","volume":"30","author":"A. Andersson","year":"2000","unstructured":"Andersson, A., Hagerup, T., Hastad, J., Petersson, O.: Tight bounds for searching a sorted array of strings. SIAM J.\u00a0Comput.\u00a030(5), 1552\u20131578 (2000)","journal-title":"SIAM J.\u00a0Comput."},{"issue":"4","key":"6_CR2","doi-asserted-by":"publisher","first-page":"448","DOI":"10.1016\/S0022-0000(73)80033-9","volume":"7","author":"M. Blum","year":"1973","unstructured":"Blum, M., Floyd, R.W., Pratt, V., Rivest, R.L., Tarjan, R.E.: Time bounds for selection. J.\u00a0Comput.\u00a0Syst.\u00a0Sci.\u00a07(4), 448\u2013461 (1973)","journal-title":"J.\u00a0Comput.\u00a0Syst.\u00a0Sci."},{"key":"6_CR3","doi-asserted-by":"crossref","unstructured":"Brodnik, A., Carlsson, S., Demaine, E., Munro, J.I., Sedgewick, R.: Resizable arrays in optimal time and space. In: WADS, p. 37 (1999)","DOI":"10.1007\/3-540-48447-7_4"},{"issue":"5","key":"6_CR4","doi-asserted-by":"publisher","first-page":"1627","DOI":"10.1137\/S0097539795294165","volume":"28","author":"A. Brodnik","year":"1999","unstructured":"Brodnik, A., Munro, J.I.: Membership in constant time and almost-minimum space. SIAM J.\u00a0Comput.\u00a028(5), 1627\u20131640 (1999)","journal-title":"SIAM J.\u00a0Comput."},{"key":"6_CR5","doi-asserted-by":"crossref","unstructured":"Carlsson, S., Munro, J.I., Poblete, P.V.: An implicit binomial queue with constant insertion time. In: SWAT, pp. 1\u201313 (1988)","DOI":"10.1007\/3-540-19487-8_1"},{"issue":"11","key":"6_CR6","doi-asserted-by":"publisher","first-page":"1343","DOI":"10.1145\/50087.50096","volume":"31","author":"J.R. Driscoll","year":"1988","unstructured":"Driscoll, J.R., Gabow, H.N., Shrairman, R., Tarjan, R.E.: Relaxed heaps: an alternative to Fibonacci heaps with applications to parallel computation. Comm.\u00a0ACM\u00a031(11), 1343\u20131354 (1988)","journal-title":"Comm.\u00a0ACM"},{"issue":"1","key":"6_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/0222001","volume":"22","author":"A. Fiat","year":"1993","unstructured":"Fiat, A., Naor, M.: Implicit O(1) probe search. SIAM J.\u00a0Comput.\u00a022(1), 1\u201310 (1993)","journal-title":"SIAM J.\u00a0Comput."},{"issue":"4","key":"6_CR8","first-page":"764","volume":"39","author":"A. Fiat","year":"1992","unstructured":"Fiat, A., Naor, M., Schmidt, J.P., Siegel, A.: Nonoblivious hashing. J.\u00a0ACM\u00a039(4), 764\u2013782 (1992)","journal-title":"J.\u00a0ACM"},{"key":"6_CR9","doi-asserted-by":"crossref","unstructured":"Franceschini, G., Grossi, R.: Optimal worst-case operations for implicit cache-oblivious search trees. In: Proc.\u00a08th WADS (2003)","DOI":"10.1007\/978-3-540-45078-8_11"},{"key":"6_CR10","doi-asserted-by":"crossref","unstructured":"Franceschini, G., Grossi, R.: No sorting? better searching! In: Proc.\u00a045th IEEE Symp.\u00a0on Foundations of Computer Science (FOCS), pp. 491\u2013498 (2004)","DOI":"10.1109\/FOCS.2004.43"},{"issue":"4","key":"6_CR11","first-page":"473","volume":"46","author":"M.L. Fredman","year":"1999","unstructured":"Fredman, M.L.: On the efficiency of pairing heaps and related data structures. J.\u00a0ACM\u00a046(4), 473\u2013501 (1999)","journal-title":"J.\u00a0ACM"},{"issue":"1","key":"6_CR12","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/BF01840439","volume":"1","author":"M.L. Fredman","year":"1986","unstructured":"Fredman, M.L., Sedgewick, R., Sleator, D.D., Tarjan, R.E.: The pairing heap: a new form of self-adjusting heap. Algorithmica\u00a01(1), 111\u2013129 (1986)","journal-title":"Algorithmica"},{"issue":"3","key":"6_CR13","first-page":"596","volume":"34","author":"M.L. Fredman","year":"1987","unstructured":"Fredman, M.L., Tarjan, R.E.: Fibonacci heaps and their uses in improved network optimization algorithms. J.\u00a0ACM\u00a034(3), 596\u2013615 (1987)","journal-title":"J.\u00a0ACM"},{"key":"6_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/3-540-45471-3_1","volume-title":"Algorithm Theory - SWAT 2002","author":"T. Hagerup","year":"2002","unstructured":"Hagerup, T., Raman, R.: An efficient quasidictionary. In: Penttonen, M., Schmidt, E.M. (eds.) SWAT 2002. LNCS, vol.\u00a02368, p. 1. Springer, Heidelberg (2002)"},{"key":"6_CR15","unstructured":"Harvey, N.J.A., Zatloukal, K.: The post-order heap. In: Proc.\u00a0FUN (2004)"},{"key":"6_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1007\/3-540-44985-X_5","volume-title":"Algorithm Theory - SWAT 2000","author":"J. Iacono","year":"2000","unstructured":"Iacono, J.: Improved upper bounds for pairing heaps. In: Halld\u00f3rsson, M.M. (ed.) SWAT 2000. LNCS, vol.\u00a01851, pp. 32\u201343. Springer, Heidelberg (2000)"},{"issue":"3","key":"6_CR17","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/0020-0190(75)90001-0","volume":"4","author":"D.B. Johnson","year":"1975","unstructured":"Johnson, D.B.: Priority queues with update and finding minimum spanning trees. Info.\u00a0Proc.\u00a0Lett.\u00a04(3), 53\u201357 (1975)","journal-title":"Info.\u00a0Proc.\u00a0Lett."},{"key":"6_CR18","unstructured":"Kaplan, H., Tarjan, R.E.: New heap data structures. Technical Report TR-597-99, Computer Science Dept., Princeton University (March 1999)"},{"key":"6_CR19","doi-asserted-by":"crossref","unstructured":"Mortensen, C.W., Pettie, S.: The complexity of implicit and space-efficient priority queues. Manuscript (2005), http:\/\/www.mpi-sb.mpg.de\/~pettie\/","DOI":"10.1007\/11534273_6"},{"issue":"1","key":"6_CR20","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1016\/0022-0000(86)90043-7","volume":"33","author":"J.I. Munro","year":"1986","unstructured":"Munro, J.I.: An implicit data structure supporting insertion, deletion, and search in $O({\\rm log}\\sp 2\\, n)$ time. J.\u00a0Comput.\u00a0Syst.\u00a0Sci.\u00a033(1), 66\u201374 (1986)","journal-title":"J.\u00a0Comput.\u00a0Syst.\u00a0Sci."},{"issue":"2","key":"6_CR21","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1016\/0022-0000(80)90037-9","volume":"21","author":"J.I. Munro","year":"1980","unstructured":"Munro, J.I., Suwanda, H.: Implicit data structures for fast search and update. J.\u00a0Comput.\u00a0Syst.\u00a0Sci.\u00a021(2), 236\u2013250 (1980)","journal-title":"J.\u00a0Comput.\u00a0Syst.\u00a0Sci."},{"issue":"2","key":"6_CR22","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1137\/S0097539700369909","volume":"31","author":"R. Pagh","year":"2001","unstructured":"Pagh, R.: Low redundancy in static dictionaries with constant query time. SIAM J.\u00a0Comput.\u00a031(2), 353\u2013363 (2001)","journal-title":"SIAM J.\u00a0Comput."},{"key":"6_CR23","unstructured":"Raman, R., Raman, V., Rao, S.S.: Succinct indexable dictionaries with applications to encoding k-ary trees and multisets. In: SODA, pp. 233\u2013242 (2002)"},{"key":"6_CR24","doi-asserted-by":"crossref","unstructured":"Raman, R., Rao, S.S.: Succinct dynamic dictionaries and trees. In: Proc.\u00a030th Int\u2019l Colloq.\u00a0on Automata, Languages and Programming (2003)","DOI":"10.1007\/3-540-45061-0_30"},{"issue":"1","key":"6_CR25","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/S0166-218X(02)00219-6","volume":"126","author":"T. Takaoka","year":"2003","unstructured":"Takaoka, T.: Theory of 2\u20133 heaps. Discrete Appl. Math.\u00a0126(1), 115\u2013128 (2003)","journal-title":"Discrete Appl. Math."},{"key":"6_CR26","first-page":"347","volume":"7","author":"J.W.J. Williams","year":"1964","unstructured":"Williams, J.W.J.: Algorithm 232 (heapsort). Comm.\u00a0ACM\u00a07, 347\u2013348 (1964)","journal-title":"Comm.\u00a0ACM"},{"issue":"3","key":"6_CR27","first-page":"615","volume":"28","author":"A.C.C. Yao","year":"1981","unstructured":"Yao, A.C.C.: Should tables be sorted? J.\u00a0ACM\u00a028(3), 615\u2013628 (1981)","journal-title":"J.\u00a0ACM"},{"key":"6_CR28","unstructured":"Zuckerman, D.: Computing Efficiently Using General Weak Random Sources. Ph.D. Thesis, The University of California at Berkeley (August 1991)"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11534273_6.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,19]],"date-time":"2025-02-19T12:03:17Z","timestamp":1739966597000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11534273_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540281016","9783540317111"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/11534273_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}