In Computer Science seminar,
we have a
on the topic
Abstract:
A priority queue Q
find-min(): Return a minimum element stored in Q.
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.
More information on the 25th Anniversary Tour of prof. Katajainen can be
found at
http://www.diku.dk/~jyrki/PE-lab/Talks/2004-Announcements/2004.10.04-16%3A10%3A45.html
.
Welcome!
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.