© 1993 by British Computer Society
| ||||||||||||||||||||||||||||||||||||||||||||||||||||
Interval Heaps
1 Department of Computer Science, University of Utrecht, PO Box 80.089, 3508 TB Utrecht, The Netherlands, 2 Department of Computer Science, University of Western Ontario, London, Ontario N6A 3K7, Canada
We present new solutions to the problems of constructing efficient implicit data structures for min-max and min-max-median priority queues. The novelty in our approach is that we use the standard heap (or priority 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 that the updating algorithms are almost the same as those for the standard heap implementation of a priority queue. The second advantage is that we can easily generalize the heap structure to accommodate multidimensional data. The third advantage is that we immediately derive optimal query algorithms for complementary-range queries. A number of applications to computational geometry are discussed. By generalizing the approach for d-dimensional data, a (dynamic) implicit data structure is obtained for complementary-range searching in 
(K) time per query and with (log n) update time, for fixed d, where K is the number of answers to a query. Several related ideas and applications are also discussed.
Received April 1988. revised June 1992.
* Department of Computer Science, University of Utrecht, PO Box 80.089, 3508 TB Utrecht, The Netherlands
Department of Computer Science, University of Western Ontario, London, Ontario N6A 3K7, Canada