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.gif>PDF (254 kB)  
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 NSN / 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.gif>HTML (Technical report)  <html.gif>HTML (Slides)  
  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},
This page was generated by Jyrki Katajainen <> on 28.10.2015.