Dynamic Online Multiselection in Internal and External Memory

We consider the dynamic version of the

online multiselection

problem for internal and external memory, in which

q

selection queries are requested on an unsorted array of

N

elements. Our internal memory result is 1-competitive with the offline result of Kaligosiet al.[ICALP 2005]. In particular, we extend the results of Barbaryet al.[ESA 2013] by supporting arbitrary

insertions

and

deletions

while supporting online

select

and

search

queries on the array. Assuming that the insertion of an element is immediately preceded by a search for that element, we show that our dynamic online algorithm performs an optimal number of comparisons, up to lower order terms and an additive

O

(

N

) term.

For the external memory model, we describe the first online multiselection algorithm that is

O

(1)-competitive. This result improves upon the work of Sibeyn [Journal of Algorithms 2006] when

q

 > 

m

, where

m

is the number of blocks that can be stored in main memory. We also extend it to support searches, insertions, and deletions of elements efficiently.