Priority queues and sorting for read-only data

Tetsuo Asano; Amr Elmasry; Jyrki Katajainen

doi:10.1007/978-3-642-38236-9_4

Priority queues and sorting for read-only data

Tetsuo Asano, Amr Elmasry, Jyrki Katajainen

Department of Computer Science

16 Citations (Scopus)

91 Downloads (Pure)

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(N ²/S + N lg S)-time sorting algorithm for this model.

Original language	English
Title of host publication	Theory and Applications of Models of Computation : 10th International Conference, TAMC 2013, Hong Kong, China, May 20-22, 2013. Proceedings
Editors	T-H. Hubert Chan, Lap Chi Lau, Luca Trevisan
Number of pages	10
Publisher	Springer
Publication date	2013
Pages	32-41
ISBN (Print)	978-3-642-38235-2
ISBN (Electronic)	978-3-642-38236-9
DOIs	https://doi.org/10.1007/978-3-642-38236-9_4
Publication status	Published - 2013
Event	10th International Conference on Theory and Applications of Models of Computation - Hong Kong, China Duration: 20 May 2013 → 22 May 2013 Conference number: 10

Conference

Conference	10th International Conference on Theory and Applications of Models of Computation
Number	10
Country/Territory	China
City	Hong Kong
Period	20/05/2013 → 22/05/2013

Series	Lecture notes in computer science
Volume	7876
ISSN	0302-9743

Access to Document

10.1007/978-3-642-38236-9_4

Priority queues and sorting for read-only dataAccepted author manuscript, 257 KBLicence: Other

Cite this

Asano, T., Elmasry, A., & Katajainen, J. (2013). Priority queues and sorting for read-only data. In T-H. H. Chan, L. C. Lau, & L. Trevisan (Eds.), Theory and Applications of Models of Computation: 10th International Conference, TAMC 2013, Hong Kong, China, May 20-22, 2013. Proceedings (pp. 32-41). Springer. Lecture notes in computer science Vol. 7876 https://doi.org/10.1007/978-3-642-38236-9_4

Priority queues and sorting for read-only data. / Asano, Tetsuo; Elmasry, Amr; Katajainen, Jyrki.

Theory and Applications of Models of Computation: 10th International Conference, TAMC 2013, Hong Kong, China, May 20-22, 2013. Proceedings. ed. / T-H. Hubert Chan; Lap Chi Lau; Luca Trevisan. Springer, 2013. p. 32-41 (Lecture notes in computer science, Vol. 7876).

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

Asano, T, Elmasry, A & Katajainen, J 2013, Priority queues and sorting for read-only data. in T-HH Chan, LC Lau & L Trevisan (eds), Theory and Applications of Models of Computation: 10th International Conference, TAMC 2013, Hong Kong, China, May 20-22, 2013. Proceedings. Springer, Lecture notes in computer science, vol. 7876, pp. 32-41, 10th International Conference on Theory and Applications of Models of Computation, Hong Kong, China, 20/05/2013. https://doi.org/10.1007/978-3-642-38236-9_4

Asano T, Elmasry A, Katajainen J. Priority queues and sorting for read-only data. In Chan T-HH, Lau LC, Trevisan L, editors, Theory and Applications of Models of Computation: 10th International Conference, TAMC 2013, Hong Kong, China, May 20-22, 2013. Proceedings. Springer. 2013. p. 32-41. (Lecture notes in computer science, Vol. 7876). doi: 10.1007/978-3-642-38236-9_4

Asano, Tetsuo ; Elmasry, Amr ; Katajainen, Jyrki. / Priority queues and sorting for read-only data. Theory and Applications of Models of Computation: 10th International Conference, TAMC 2013, Hong Kong, China, May 20-22, 2013. Proceedings. editor / T-H. Hubert Chan ; Lap Chi Lau ; Luca Trevisan. Springer, 2013. pp. 32-41 (Lecture notes in computer science, Vol. 7876).

@inproceedings{c106dad173514cc2b38069552b94058a,

title = "Priority queues and sorting for read-only data",

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(N 2/S + N lg S)-time sorting algorithm for this model.",

author = "Tetsuo Asano and Amr Elmasry and Jyrki Katajainen",

year = "2013",

doi = "10.1007/978-3-642-38236-9_4",

language = "English",

isbn = "978-3-642-38235-2",

series = "Lecture notes in computer science",

publisher = "Springer",

pages = "32--41",

editor = "Chan, {T-H. Hubert} and Lau, {Lap Chi} and Luca Trevisan",

booktitle = "Theory and Applications of Models of Computation",

note = "10th International Conference on Theory and Applications of Models of Computation, TAMC 2013 ; Conference date: 20-05-2013 Through 22-05-2013",

}

TY - GEN

T1 - Priority queues and sorting for read-only data

AU - Asano, Tetsuo

AU - Elmasry, Amr

AU - Katajainen, Jyrki

N1 - Conference code: 10

PY - 2013

Y1 - 2013

N2 - 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(N 2/S + N lg S)-time sorting algorithm for this model.

AB - 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(N 2/S + N lg S)-time sorting algorithm for this model.

U2 - 10.1007/978-3-642-38236-9_4

DO - 10.1007/978-3-642-38236-9_4

M3 - Article in proceedings

SN - 978-3-642-38235-2

T3 - Lecture notes in computer science

SP - 32

EP - 41

BT - Theory and Applications of Models of Computation

A2 - Chan, T-H. Hubert

A2 - Lau, Lap Chi

A2 - Trevisan, Luca

PB - Springer

T2 - 10th International Conference on Theory and Applications of Models of Computation

Y2 - 20 May 2013 through 22 May 2013

ER -

Priority queues and sorting for read-only data

Abstract

Conference

Access to Document

Fingerprint

Cite this