| Priority queues and sorting for read-only data | |
| Authors: | Tetsuo Asano, Amr Elmasry, and Jyrki Katajainen |
| Published in: | Proceedings of the 10th Annual Conference on Theory and Applications of Models of Computation, Lecture Notes in Computer Science 7876, Springer-Verlag (2013), 32-41 |
| Full text: |  PDF (254 kB) |
| DOI: | 10.1007/978-3-642-38236-9_4 |
| Copyright: | © Springer-Verlag GmbH Berlin Heidelberg |
| Abstract: | We revisit the random-access-machine model in which the input is given on a read-only random-access media, the output is to be produced to a write-only sequential-access media, and in addition there is a limited random-access workspace. The length of the input is N elements, the length of the output is limited by the computation itself, and the capacity of the workspace is O(S + w) bits, where S is a parameter specified by the user and w is the number of bits per machine word. We present a state-of-the-art priority queue—called an adjustable navigation pile—for this model. Under some reasonable assumptions, our priority queue supports minimum and insert in O(1) worst-case time and extract in O(N / S + lg S) worst-case time, where lg N ≤ S ≤ N / lg N. We also show how to use this data structure to simplify the existing optimal O(N2 / S + N lg S)-time sorting algorithm for this model. |
| Related: |  HTML (Technical report) HTML (Slides) |
| BibLATEX: | @inproceedings{AEK2013C,
author = {Tetsuo Asano and Amr Elmasry and Jyrki Katajainen},
title = {Priority queues and sorting for read-only data},
booktitle = {Proceedings of the 10th Annual Conference on Theory and
Applications of Models of Computation},
series = {Lecture Notes in Computer Science},
volume = {7876},
publisher = {Springer-Verlag},
year = {2013},
pages = {32--41},
}
|