Priority Queues and Sorting for Read-Only Data
Tetsuo Asano, Amr Elmasry, Jyrki Katajainen · Lecture notes in computer science · 2013
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 \leq S \leq 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. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.