All nearest smaller values
In
Example
Suppose that the input is the binary van der Corput sequence
- 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15.
The first element of the sequence (0) has no previous value. The nearest (only) smaller value previous to 8 and to 4 is 0. All three values previous to 12 are smaller, but the nearest one is 4. Continuing in the same way, the nearest previous smaller values for this sequence (indicating the nonexistence of a previous smaller value by a dash) are
- —, 0, 0, 4, 0, 2, 2, 6, 0, 1, 1, 5, 1, 3, 3, 7.
In most applications, the positions of the nearest smaller values, and not the values themselves, should be computed, and in many applications the same computation should be computed for the reversal of the sequence in order to find the following smaller value that is closest in the sequence.
Applications
Berkman, Schieber & Vishkin (1993) mention many other problems that may be solved efficiently in parallel using a nearest smaller values computation. Among them, they include the following:
- Merge algorithms, computing the merge step of a merge sort. The input to these algorithms consists of two sorted arrays of numbers; the desired output is the same set of numbers in a single sorted array. If one concatenates the two sorted arrays, the first in ascending order and the second in descending order, then the predecessor of each value in the output is either its closest previous smaller value or its closest following smaller value (whichever of the two is larger), and the position of each value in the sorted output array may easily be calculated from the positions of these two nearest smaller values.
- Construction of binary searching. The Cartesian tree of a sequence of values has a node for each value. The root of the tree is the minimum value of the sequence; for every other node, the parent of the node is either its closest previous smaller value or its closest following smaller value (whichever of the two exists and is larger). Thus, Cartesian trees may be constructed in linear time based on an all nearest smaller values algorithm.
- Matching parentheses. If a sequence of open and close parenthesis characters is given as input, together with the nesting depth of each parenthesis, then the match to each open parenthesis is the next close parenthesis with no larger nesting depth, so it can be found by an all nearest smaller values computation that breaks ties in favor of close parentheses. If the nesting depths are not given, they can be calculated using a prefix sumcomputation.
Similar techniques may also be applied to problems of polygon triangulation, convex hull construction (parallelizing the sequential Graham scan convex hull algorithm), reconstruction of trees from two of the trees' traversal orderings, and quadtree construction.[1]
Sequential algorithm
On a sequential computer, all nearest smaller values may be found by using a
S = new empty stack data structure for x in the input sequence do while S is nonempty and the top element of S is greater than or equal to x do pop S if S is empty then x has no preceding smaller value else the nearest smaller value to x is the top element of S push x onto S
Despite having a nested loop structure, the running time of this algorithm is linear, because every iteration of the inner loop removes an item that had been added in some previous iteration of the outer loop. It is closely related to an algorithm of Knuth for sorting with a stack (for inputs that can be sorted in this way).[2]
An even simpler linear-time sequential algorithm (Barbay, Fischer & Navarro (2012), Lemma 1) does not even need a stack; it assumes that the input sequence is given as an array A[1,n]
of size n
, and stores the index j
of the preceding smaller value of the i
th value A[i]
in P[i]
. We assume an artificial overall minimum at A[0]
:
for i from 1 to n: j = i-1 while A[j] >= A[i]: j = P[j] P[i] = j
Parallel algorithms
Notes
- ^ Bern, Eppstein & Teng (1999).
- ^ Knuth, Donald (1968), "Vol. 1: Fundamental Algorithms", The Art of Computer Programming, Reading, Mass.: Addison-Wesley.
- ^ Kravets & Plaxton (1996).
- ^ He & Huang (2001).
References
- Barbay, Jeremy; Fischer, Johannes; Navarro, Gonzalo (2012), "LRM-Trees: Compressed indices, adaptive sorting, and compressed permutations", Theoretical Computer Science, 459: 26–41, .
- Berkman, Omer; Matias, Yossi; Ragde, Prabhakar (1998), "Triply-logarithmic parallel upper and lower bounds for minimum and range minima over small domains", Journal of Algorithms, 28 (2): 197–215, .
- Berkman, Omer; .
- Bern, Marshall; .
- S2CID 17752833.
- He, Xin; Huang, Chun-Hsi (2001), "Communication efficient BSP algorithm for all nearest smaller values", Journal of Parallel and Distributed Computing, 61 (10): 1425–1438, .
- Kravets, D.; Plaxton, C. G. (1996), "All nearest smaller values on the hypercube", IEEE Trans. Parallel and Distributed Systems, 7 (5): 456–462, .
- .