{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T14:43:08Z","timestamp":1742913788286,"version":"3.40.3"},"publisher-location":"Cham","reference-count":12,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319218397"},{"type":"electronic","value":"9783319218403"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-21840-3_8","type":"book-chapter","created":{"date-parts":[[2015,7,27]],"date-time":"2015-07-27T09:57:38Z","timestamp":1437991058000},"page":"91-102","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Strictly Implicit Priority Queues: On\u00a0the\u00a0Number of Moves and Worst-Case Time"],"prefix":"10.1007","author":[{"given":"Gerth St\u00f8lting","family":"Brodal","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jesper Sindahl","family":"Nielsen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jakob","family":"Truelsen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,7,28]]},"reference":[{"key":"8_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1007\/978-3-642-40273-9_11","volume-title":"Space-Efficient Data Structures, Streams, and Algorithms","author":"GS Brodal","year":"2013","unstructured":"Brodal, G.S.: A survey on priority queues. In: Brodnik, A., L\u00f3pez-Ortiz, A., Raman, V., Viola, A. (eds.) Ianfest-66. LNCS, vol. 8066, pp. 150\u2013163. Springer, Heidelberg (2013)"},{"key":"8_CR2","doi-asserted-by":"crossref","unstructured":"Brodal, G.S., Fagerberg, R., Jacob, R.: Cache oblivious search trees via binary trees of small height. In: Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 39\u201348 (2002)","DOI":"10.7146\/brics.v8i36.21696"},{"key":"8_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"527","DOI":"10.1007\/978-3-642-35261-4_55","volume-title":"Algorithms and Computation","author":"GS Brodal","year":"2012","unstructured":"Brodal, G.S., Nielsen, J.S., Truelsen, J.: Finger search in the implicit model. In: Chao, K.-M., Hsu, T.-S., Lee, D.-T. (eds.) ISAAC 2012. LNCS, vol. 7676, pp. 527\u2013536. Springer, Heidelberg (2012)"},{"key":"8_CR4","doi-asserted-by":"crossref","unstructured":"Brodal, G.S., Nielsen, J.S., Truelsen, J.: Strictly implicit priority queues: On the number of moves and worst-case time (2015). CoRR, abs\/1505.00147","DOI":"10.1007\/978-3-319-21840-3_8"},{"key":"8_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/3-540-19487-8_1","volume-title":"SWAT 88","author":"S Carlsson","year":"1988","unstructured":"Carlsson, S., Munro, J.I., Poblete, P.V.: An implicit binomial queue with constant insertion time. In: Karlsson, R., Lingas, A. (eds.) SWAT 88. LNCS, vol. 318, pp. 1\u201313. Springer, Heidelberg (1988)"},{"key":"8_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1007\/BFb0015429","volume-title":"Algorithms and Computations","author":"S Carlsson","year":"1995","unstructured":"Carlsson, S., Sundstr\u00f6m, M.: Linear-time in-place selection in less than 3n. In: Staples, J., Katoh, N., Eades, P., Moffat, A. (eds.) ISAAC 1995. LNCS, vol. 1004, pp. 244\u2013253. Springer, Heidelberg (1995)"},{"key":"8_CR7","unstructured":"Edelkamp, S., Elmasry, A., Katajainen, J.: Ultimate binary heaps, Manuscript (2013)"},{"issue":"4","key":"8_CR8","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1007\/s00224-006-1311-1","volume":"40","author":"G Franceschini","year":"2007","unstructured":"Franceschini, G.: Sorting stably, in place, with $$O(n \\log n)$$ comparisons and $$O(n)$$ moves. Theory of Computing Systems 40(4), 327\u2013353 (2007)","journal-title":"Theory of Computing Systems"},{"key":"8_CR9","doi-asserted-by":"crossref","unstructured":"Franceschini, G., Munro, J.I.: Implicit dictionaries with $$O(1)$$ modifications per update and fast search. In: Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 404\u2013413 (2006)","DOI":"10.1145\/1109557.1109603"},{"issue":"1","key":"8_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/321992.321993","volume":"24","author":"DB Johnson","year":"1977","unstructured":"Johnson, D.B.: Efficient algorithms for shortest paths in sparse networks. Journal of the ACM 24(1), 1\u201313 (1977)","journal-title":"Journal of the ACM"},{"key":"8_CR11","unstructured":"Harvey, N.J.A., Zatloukal, K.C.: The post-order heap. In: 3rd International Conference on Fun with Algorithms (2004)"},{"issue":"6","key":"8_CR12","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1145\/512274.512284","volume":"7","author":"JWJ Williams","year":"1964","unstructured":"Williams, J.W.J.: Algorithm 232: Heapsort. Communications of the ACM 7(6), 347\u2013348 (1964)","journal-title":"Communications of the ACM"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-21840-3_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,21]],"date-time":"2023-02-21T09:59:37Z","timestamp":1676973577000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-21840-3_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319218397","9783319218403"],"references-count":12,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-21840-3_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"28 July 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}