Data structural bootstrapping, linear path compression, and catenable heap ordered double e.pdf

Data Structural Bootstrapping, Linear Path Compression, and Catenable Heap Ordered Double Ended Queues1 Adam L. Buchsbaum2 Rajamani Sundar3 Robert E. Tarjan4 Research Report CS-TR-381-92 September 1992 Abstract A deque with heap order is a linear list of elements with real-valued keys which allows inser- tions and deletions of elements at both ends of the list. It also allows the ndmin (equivalently ndmax) 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 (maxd- eque). Whereas implementing mindeques in constant time per operation is a solved problem, catenating mindeques in sublogarithmic time has until now remained open. This paper provides an ecient implementation of catenable mindeques, yielding constant amortized time per operation. The important algorithmic technique employed is an idea which is best described as data structural bootstrapping: We abstract mindeques so that their elements represent other mindeques, eecting catenation while preserving heap order. The eciency of the resulting data structure depends upon the complexity of a special case of path compression which we prove requires linear time. 1An extended abstract of this paper will appear in the 33rd IEEE Foundations of Computer Science, 25-27 October, 1992. 2Supported by a Fannie and John Hertz Foundation fellowship, National Science Foundation Grant No. CCR-8920505, and the Center for Discrete Mathematics and Theoretical Computer Science (DIMACS) under NSF-STC88-09648. 3Also aliated with DIMACS, Rutgers University, Piscataway, NJ 08855. Supported by DIMACS under NSF-STC88-09648. 4Also aliated with NEC Research Institute, 4 Independence Way, Princeton, NJ 08540. Research at Princeton University partially supported by the National Science Foundation, Grant No. CCR-8920505, the Oce of Naval Research, Contract No. N00014-91-J-1463, and by DIMACS under NSF-STC88-09648.