INTERVAL HEAPS

We present new solutions to the problems of constructing efficient imp licit data structures for min-max and min-max-median priority queues. The novelty in our approach is that we use the standard heap (or prior ity queue) structure with multiple values at the nodes. This technique yields a consistent approach to the implementation of min-max and min -max-median priority queues. The first advantage of this approach is t hat the updating algorithms are almost the same as those for the stand ard heap implementation of a priority queue. The second advantage is t hat we can easily generalize the heap structure to accommodate multidi mensional data. The third advantage is that we immediately derive opti mal query algorithms for complementary-range queries. A number of appl ications to computational geometry are discussed. By generalizing the approach for d-dimensional data, a (dynamic) implicit data structure i s obtained for complementary-range searching in THETA(K) time per quer y and with THETA(log n) update times, for fixed d, where K is the numb er of answers to a query. Several related ideas and applications are a lso discussed.