McGill University - School of Computer Science

Algorithms Seminar 2002

Everybody is welcome!

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.

Direct questions, comments, additions to and removals from the mailing list, and suggestions for speakers to us at beezer(at) , or .
Web Address: