2026-07-22T16:50:26Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24473 2025-12-16T13:59:34Z ddc:004 open_access

External-Memory Priority Queues with Optimal Insertions Brodal, Gerth Stølting Goodrich, Michael T. Iacono, John Lo, Jared Meyer, Ulrich Pagan, Victor Sitchinava, Nodari Svenning, Rolf priority queues external memory cache aware amortized complexity We present an external-memory priority queue structure supporting Insert and DeleteMin with amortized 𝒪(1) and 𝒪(lg N) comparisons, respectively, and amortized 𝒪(1/B) and 𝒪(1/B log_{M/B} N/B) I/Os, respectively. Here, M is the size of the internal memory, B is the block size of I/Os between internal and external memory, and N is the number of elements in the priority queue just before an operation is performed. Previous external-memory priority queues required amortized 𝒪(lg N) comparisons and 𝒪(1/B log_{M/B} N/B) I/Os for both Insert and DeleteMin. The construction requires the minimal assumption M ≥ 2B. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Gerth Stølting Brodal and Michael T. Goodrich and John Iacono and Jared Lo and Ulrich Meyer and Victor Pagan and Nodari Sitchinava and Rolf Svenning 2025 Is Part Of LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2025.5 urn:nbn:de:0030-drops-244734 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.5 eng https://creativecommons.org/licenses/by/4.0/legalcode