Data Structural Bootstrapping, Linear Path Compression, and Catenable Heap Ordered Double Ended Queues
Report ID: TR-381-92Author: Buchsbaum, Adam L. / Tarjan, Robert E. / Sundar, Rajamani
Date: 1992-07-00
Pages: 12
Download Formats: |Postscript|
Abstract:
A {em deque with heap order} is a linear list of elements with real-valued keys which allows insertions and deletions of elements at both ends of the list. It also allows the {em findmin} (equivalently {em findmax}) operation, which returns the element of least (greatest) key, but it does not allow a general {em deletemin} ({em deletemax}) operation. Such a data structure is also called a {em mindeque} ({em maxdeque}). 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 efficient implementation of catenable mindeques, yielding constant amortized time per operation. The important algorithmic technique employed is an idea which is best described as {em data structural bootstrapping}: We abstract mindeques so that their elements represent other mindeques, effecting catenation while preserving heap order. The efficiency of the resulting data structure depends upon the complexity of a special case of path compression which we prove requires linear time.