Title: Anatomy of a worst-case efficient priority queue
Speaker: Jyrki Katajainen
Time: Tuesday, 12 October 2004, 16.30 - 17.30
Place: Lille UP1
Abstract: A priority queue Q<element, ordering> is a data structure which stores a set of elements under some ordering function such that, among other things, the following operations are supported:
find-min(): Return a minimum element stored in Q.
insert(e): Insert element e into Q and return its position for later use.
delete-min(): Remove a minimum element from Q.
delete(p): Remove the element stored at position p from Q.
decrease(p, e): Replace the element stored at position p with a
smaller element e.
In many graph applications a priority queue is needed which achieves an amortized cost of O(1) for decrease() and O(log n) for delete-min(). In such situations a Fibonacci heap could be used.
In a recent joint paper with Amr Elmasry and Claus Jensen, we studied priority queues having the same efficiency in the worst case. In my presentation I will describe the internals of one such data structure, called a pruned binomial queue, which is a forest of pruned binomial trees. Most of the ideas used in the data structure are borrowed from the paper on relaxed heaps by Driscoll, Gabow, Shrairman, and Tarjan from 1988. Using pruned binomial trees as the basic building blocks, we have been able to develop a priority queue for which the constant factors in asymptotic estimates are almost optimal. However, already pruned binomial queues are complicated, so my hope is that the presentation would generate some ideas how the data structure could be simplified.
Jubilee home page: [html]
PE-lab's home page: http://www.diku.dk/~jyrki/PE-lab/