Published on *Computer Science Department at Princeton University* (http://www.cs.princeton.edu)

Report ID:

TR-381-92

Authors:

Date:

June 1992

Pages:

12

Download Formats:

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.