DATA-STRUCTURAL BOOTSTRAPPING, LINEAR PATH COMPRESSION, AND CATENABLEHEAP-ORDERED DOUBLE-ENDED QUEUES

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, bur it does not a llow a general deletemin (deletemax) operation. Such a data structure is also called a mindeque (maxdeque). Whereas implementing heap-ordere d deques in constant time per operation is a solved problem, catenatin g heap-ordered deques in sublogarithmic time has remained open until n ow. This paper provides an efficient implementation of catenable heap- ordered deques, yielding constant amortized time per operation. The im portant algorithmic technique employed is an idea that we call data-st ructural bootstrapping: we abstract heap-ordered deques by representin g them by their minimum elements, thereby reducing catenation to simpl e insertion. The efficiency of the resulting data structure depends up on the complexity elf a special case of path compression that we prove takes linear time.