A deque with heap order is a linear list of elements with real-valued keys that allows insertions and deletions of elements at both ends of the list. It also allows the findmin (alternatively findmax) operation, which returns the element of least (greatest) key, but it does not allow a general deletemin (deletemax) operation. Such a data structure is also called a mindeque (maxdeque). Whereas implementing heap-ordered deques in constant time per operation is a solved problem, catenating heap-ordered deques in sublogarithmic time has remained open until now. This paper provides an efficient implementation of catenable heap-ordered deques, yielding constant amortized time per operation. The important algorithmic technique employed is an idea that we call data-structural bootstrapping; we abstract heap-ordered deques by representing them by their minimum elements, thereby reducing catenation to simple insertion, The efficiency of the resulting data structure depends upon the complexity of a special case of path compression that we prove takes linear time.

This paper studies the problem of representing sets over an ordered universe by unique binary search trees, so that dictionary operations can be performed efficiently on any set. Although efficient randomized solutions to the problem are known, its deterministic complexity has been open. The paper exhibits representations that permit the execution of dictionary operations in optimal deterministic time when the dictionary is sufficiently sparse or sufficiently dense. The results demonstrate an exponential separation between the deterministic and randomized complexities of the problem. Unique representations are applied to obtain efficient data structures for maintaining a dynamic collection of sets/sequences under queries that test the equality of a pair of objects. The data structure for set equality testing tests equality of sets in constant time and processes set updates in $O(\log m)$ amortized time and $O(\log m)$ space, where m denotes the total number of updates performed. It is based on an efficient implementation of cascades of CONS operations on uniquely stored S-expressions. The data structure for sequence equality testing tests equality of sequences in constant time and processes updates in $O(\sqrt {n\log m} = \log m)$ amortized time and $O(\sqrt n )$ amortized space where n denotes the length of the sequence that is updated and m denotes the total number of updates performed.

The authors provide an efficient implementation of catenable mindeques. To prove that the resulting data structure achieves constant amortized time per operation, they consider order preserving path compression. They prove a linear bound on deque ordered spine-only path compression, a case of order persevering path compression employed by the data structure.>

A fundamental open question in data structures concerns the existence of a dictionary data structure that processes the operations in constant amortized time and uses space polynomial in the dictionary size. The complexity of the dictionary problem is studied under a multilevel hashing model that is based on A.C. Yao's (1981) cell probe model, and it is proved that dictionary operations require log-algorithmic amortized time jn this model. The model encompasses many known solutions to the dictionary problem, and the result is the first nontrivial lower bound for the problem in a reasonably general model that takes into account the limited wordsize of memory locations and realistically measures the cost of update operations. This lower bound separates the deterministic and randomized complexities of the problem under this model.>

Given an ordered universe U, we study the problem of representing each subset of U by a unique binary search tree so that dictionary operations can be performed efficiently.While efficient randomized solutions to the problem are known, its deterministic complexity has remained unexplored.We exhibit representations that permit the execution of dictionary operations in optimal deterministic time when the dictionary is sufficiently sparse or sufficiently dense.Our results demonstrate an exponential separation between the deterministic and randomized complexities of the problem.We apply unique representations to obtain efficient data structures for maintaining a collection of sets/sequences under queries that test the equality of a pair of objects.Our data structure for set equality-testing is based on an efficient implementation of cascades of CONS operations on uniquely stored Sexpressions.

Nearly tight upper and lower bounds on the maximum number of various rotational operations that can be performed on a binary tree are proved. One of the lower bound results refutes D.E. Sleator's turn conjecture for binary trees (see R.E. Tarjan, SIAM J. Alg. Disc. Meth., vol.2, p.306-318, 1985). The upper bound results are used to derive an inverse Ackerman bound for Tarjan's deque conjecture on the performance of the splay tree. Two new proofs of Tarjan's scanning theorem are provided. One proof generalizes the theorem, whereas the other is a simple, potential-based proof.>