We consider space-bounded computations on a random-access machine, where the input is given on a read-only random-access medium, the output is to be produced to a write-only sequential-access medium, and the available workspace allows random reads and writes but is of limited capacity. The length of the input is N elements, the length of the output is limited by the computation, and the capacity of the workspace is O ( S ) bits for some predetermined parameter S ≥ lg N . We present a state-of-the-art priority queue—called an adjustable navigation pile —for this restricted model. This priority queue supports M inimum in O (1) time, C onstruct in O ( N ) time, and E xtract - min in O ( N / S + lg S ) time for any S ≥ lg N . The priority queue can be further augmented in O ( N ) time to deal with a batch of at most S elements in a specified range of values at a time, and allow to I nsert (activate) or E xtract (deactivate) an element among these elements, such that I nsert and E xtract take O ( N / S + lg S ) time for any S ≥ lg N . We show how to use our data structure to sort N elements and to compute the convex hull of N points in the Euclidean plane in O ( N 2 / S + N lg S ) time for any S ≥ lg N . Following a known lower bound for the space-time product of any branching program for finding unique elements, both our sorting and convex-hull algorithms are optimal. The adjustable navigation pile has turned out to be useful when designing other space-efficient algorithms, and we expect that it will find its way to yet other applications.

We study the problem of constructing a binary heap in an array using only a small amount of additional space. Let N denote the size of the input, M the capacity of the cache, and B the width of the cache lines of the underlying computer, all measured as numbers of elements. We show that there exists an in-place heap-construction algorithm that runs in Θ(N) worst-case time and performs at most 1.625N+o(N) element comparisons, 1.5N+o(N) element moves, N/B+O(N/M·lgN) cache misses, and 1.375N+o(N) branch mispredictions. The same bound for the number of element comparisons was derived and conjectured to be optimal by Gonnet and Munro; however, their algorithm requires Θ(N) pointers. For a tuning parameter S, the idea is to divide the input into a top tree of size Θ(N/S) such that each of its leaves root a bottom tree of size Θ(S)⁠. When S=Θ(lgN/lglgN)⁠, we can convert the bottom trees into heaps one by one by packing the extra space needed in a few words, and subsequently use Floyd's sift-down procedure to adjust the heap order at the upper levels. In addition to our theoretical findings, we also compare different heap-construction alternatives in practice.

Summary Even a rough literature review reveals that there are many alternative ways of implementing a binary heap, the fundamental priority‐queue structure loved by us all. Which one of these alternatives is the best in practice? The opinions of crowd‐pullers and textbook authors are aligned: use an array. Of course, the correct answer is ‘it depends’. To get from opinions to facts, a framework—a set of class templates—was written that provides a variety of customization options so it could be used to realize a large part of the proposed variants. Also, some of the derived implementations were performance benchmarked. From this work, three conclusions can be drawn: (i) It is difficult to achieve space efficiency and speed at the same time. If n denotes the current number of values in the data structure, ϵ is a small positive real, ϵ < 1, and denotes the size of the values of type in bytes, space efficiency means bytes of space, and speed means O(lgn) worst‐case time per push and pop. (ii) If an array‐based solution is sufficient, Williams' original program from 1964 is still to this day hard to beat. (iii) Sometimes a linked structure and clever programming is a viable option. If the binary‐heap variant you need is not available at the software library you are using, reading this essay might save you some headaches. Copyright © 2016 John Wiley & Sons, Ltd.

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.

We introduce a framework for reducing the number of element comparisons performed in priority-queue operations. In particular, we give a priority queue which guarantees the worst-case cost of O (1) per minimum finding and insertion, and the worst-case cost of O (log n ) with at most log n + O (1) element comparisons per deletion, improving the bound of 2 log n + O (1) known for binomial queues. Here, n denotes the number of elements stored in the data structure prior to the operation in question, and log n equals log 2 (max {2, n}). As an immediate application of the priority queue developed, we obtain a sorting algorithm that is optimally adaptive with respect to the inversion measure of disorder, and that sorts a sequence having n elements and I inversions with at most n log ( I / n ) + O ( n ) element comparisons.

Shows that the use of the lazy list processing technique from the world of functional languages allows, under certain conditions, the package-merge algorithm to be executed in much less space than is indicated by the O(nL) space worst-case bound. For example, the revised implementation generates a 32-bit limited code for the TREC distribution within 15 Mb of memory. It is also shown how a second observation-that in large-alphabet situations it is often the case that there are many symbols with the same frequency-can be exploited to further reduce the space required, for both unlimited and length-limited coding. This second improvement allows calculation of an optimal length-limited code for the TREC word distribution in under 8 Mb of memory; and calculation of an unrestricted Huffman code in under 1 Mb of memory.

Text compression is often done using a fixed, previously formed dictionary (code book) that expresses which substrings of the text can be replaced by code words. There always exists an optimal solution for text-encoding problem. Due to the long processing times of the various optimal algorithms, several heuristics have been proposed in the literature. In this paper, the worst-case compression gains obtained by the longest match and the greedy heuristics for various types of dictionaries is studied. For general dictionaries, the performance of the heuristics can be almost the weakest possible. In practice, however, the dictionaries have usually properties that lead to a space-optimal or near-space-optimal coding result with the heuristics.

In many situations text compression is carried out with a previously formed fixed dictionary (code book) expressing those often-occurring substrings of a text which are to be replaced by code words. The problem of encoding a text in a space-optimal manner is equivalent to the problem of finding a shortest path between a given pair of vertices in an acyclic and bandwidth-limited network. By combining an algorithm for finding shortest paths with the string matching algorithm of Aho and Corasick,1 a time-efficient approximation algorithm for the space-optimal encoding is obtained. The performance of the approximation algorithm depends on the amount of storage space available in the fast memory of a computer. With an unrestricted, though at most linear working storage on the length of the input text, a space-optimal encoding is obtained. However, even a fixed internal memory of moderate size guarantees almost optimal compression, and in spite of this the running time of the algorithm is comparable to that of the longest match heuristic.

We prove that a $T(n)$ time-bounded, $S(n)$ space-bounded and $U(n)$ output-length-bounded Turing machine can be simulated in $O(T(n) + (n + U(n))\log \log S(n))$ time by a random access machine (with no multiplication or division instructions) under the logarithmic cost criterion.

Abstract Parsing can be applied to compress source programs. A suitably encoded parse tree, together with the symbol table, constitutes a very compact representation of the program. The paper reports a Prolog implementation of the method, including automatic, syntax‐directed, encoder and decoder generators. The test results show compression gains of 50–60 per cent.