| DATE: | Wednesday October 9th, 2002 |
| TIME: | 3:30 PM - 4:30 PM |
| PLACE: | McConnell 320 |
| TITLE: | Queaps |
| SPEAKER: | John Iacono, Polytechnic University, New York |
I will present a new priority queue data structure, the Queap,
that executes insertion in $O(1)$ amortized time and Extract-min in
$O(\log (k+2))$ amortized time if there are $k$ items that have been in
the heap longer than the item to be extracted. Thus if the operations
on the queap are first-in first-out, as on a queue, each operation
will execute in constant time. This idea of trying to make operations
on the least recently accessed items fast, which we call the queueish
property, is a natural complement to the working set property of
certain data structures, such as splay trees and pairing heaps, where
operations on the most recently accessed data execute quickly.
However, we show that the queueish property is in some sense
more difficult than the working set property by demonstrating that it
is impossible to create a queueish binary search tree, but that many
search data structures can be made almost queueish
with a $O(\log\log{n})$ amortized extra cost per operation.
This is joint work with Stefan Langerman.