Data Structural Bootstrapping, Linear Path Compression, and Catenable Heap Ordered Double Ended Queues

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.