Al. Buchsbaum et al., DATA-STRUCTURAL BOOTSTRAPPING, LINEAR PATH COMPRESSION, AND CATENABLEHEAP-ORDERED DOUBLE-ENDED QUEUES, SIAM journal on computing, 24(6), 1995, pp. 1190-1206
Citations number
29
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods",Mathematics
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.